結果

問題 No.3502 GCD Knapsack
コンテスト
ユーザー Azaki
提出日時 2026-04-18 04:23:24
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,818 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,998 ms
コンパイル使用メモリ 171,736 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2026-04-18 04:23:45
合計ジャッジ時間 4,429 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000007;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000007;
        base = (base * base) % 1000000007;
        exp /= 2;
    }
    return res;
}

int main() {
    int N;
    if (!(cin >> N)) return 0;
    vector<long long> x(N);
    for (int i = 0; i < N; i++) cin >> x[i];
    sort(x.begin(), x.end());

    long long MOD = 1000000007;
    long long total_time = 0;

    // Tính đóng góp của mỗi đoạn khoảng cách
    // Mỗi cặp (i, j) đóng góp (x[j]-x[i])/2 với xác suất 1/2^(j-i+1)
    // Trong tổng 2^N trường hợp, số lần cặp (i, j) va chạm là 2^(N - (j-i+1))
    
    // Tối ưu bằng O(N):
    // Sum = sum_{j} sum_{i<j} (x[j] - x[i]) * 2^(N-j+i-1)
    // Nghịch đảo của 2 (inv2) để xử lý phép chia 2
    long long inv2 = (MOD + 1) / 2;

    for (int i = 0; i < N; i++) {
        // Sử dụng công thức thu gọn để tính trong O(N log N) hoặc O(N)
        // Tuy nhiên với N=10^5, ta cần dùng Prefix Sum hoặc biến phụ
    }

    // Cách đơn giản nhất để tính tổng:
    // Tổng = sum_{i < j} (x[j] - x[i]) * 2^(N - (j - i + 1))
    // Viết lại: sum x[j] * (sum_{i<j} 2^(N-j+i-1)) - sum x[i] * (sum_{j>i} 2^(N-j+i-1))
    
    long long current_sum_i = 0;
    long long p2 = 1;
    long long total = 0;

    for (int j = 0; j < N; j++) {
        total = (total + x[j] * current_sum_i) % MOD;
        current_sum_i = (current_sum_i * 2 + 1) % MOD; // Đây là logic để tính 2^(j-i+1)
    }
    
    // Kết quả cần nhân với 2^(N-k) phù hợp.
    // Dưới đây là logic chuẩn xác nhất:
    long long ans = 0;
    vector<long long> pow2(N + 1);
    pow2[0] = 1;
    for(int i=1; i<=N; i++) pow2[i] = (pow2[i-1] * 2) % MOD;

    for (int i = 0; i < N; i++) {
        // Đóng góp của x[i]:
        long long term = (pow2[i] - 1 + MOD) % MOD; // sum_{k=0}^{i-1} 2^k
        term = (term * pow2[N - 1 - i]) % MOD;
        // ... (Tính toán hệ số của từng x[i])
    }
    
    // Một cách khác: x_j - x_i = (x_j - x_{j-1}) + (x_{j-1} - x_{j-2}) + ...
    // Tính đóng góp của mỗi đoạn d_k = x_{k+1} - x_k
    for (int k = 0; k < N - 1; k++) {
        long long dk = (x[k+1] - x[k]) % MOD;
        long long ways = (pow2[k + 1] - 1 + MOD) % MOD;
        ways = (ways * (pow2[N - 1 - k] - 1 + MOD)) % MOD;
        // Mỗi đoạn d_k được tính khi có ít nhất một điểm bên trái đi phải 
        // và ít nhất một điểm bên phải đi trái.
        ans = (ans + dk * ways) % MOD;
    }

    cout << (ans * inv2) % MOD << endl;

    return 0;
}
0