ABC384 F 题解

litjohn · 2024-12-15 09:18:44 · 题解

一种思路：先考虑不除的情况下的总和即

，再去除掉被除掉的部分。

发现当存在一对数的和（设为 x）是 2^i 的整数倍时，总和要去掉 \frac{x}{2^i}.

且仅当存在这种情况时，总和需要被去除。

那么就可以写代码了。

枚举每一个可能会产生贡献的 2^i，求序列中模它余 k 的数的后缀和与后缀出现次数。用当前数计算贡献然后去除总和。

怎么看当前数可能产生的贡献呢？假设它模当前的 2^i 同余 c，那么那些与它的和被当前的 2^i 整除的数模 2^i 同余 2^i-c。

#include <bits/stdc++.h>

using namespace std;
int n;
unsigned long long ans;
array<unsigned int, 200005> a;
array<int, 20000005> cnt;
array<unsigned long long, 20000005> sum;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = n; i > 0; --i) {
        cin >> a[i];
        ans += 1ll * (n + 1) * a[i];
    }

    for (int i = 1; i < 25; ++i) {
        for (int j = 1; j <= n; ++j) {
            unsigned int x = a[j] & ((1 << i) - 1);
            cnt[x]++;
            sum[x] += a[j];

            unsigned int c;
            if (x == 0) {
                c = 0;
            } else {
                c = (1 << i) - x;
            }

            ans -= (1ll * cnt[c] * a[j] + sum[c]) >> i;
        }

        for (int j = 1; j <= n; ++j) {
            unsigned int x = a[j] & ((1 << i) - 1);
            cnt[x] = 0;
            sum[x] = 0;
        }
    }
    cout << ans;
    return 0;
}