位思想

Double Sum 2

题意： 求所有有序对一直除以 $2$ 直至为奇数后的值的和。

需要发现一个性质，设 $f_i$ 表示所有能被 $2^i$ 整除的和，则 $f_{i + 1} - f_i$ 表示恰好有 $i$ 个因子 $2$ 的和，那么对于这些和，对答案的贡献就是 $\dfrac{f_i}{2^i}$。

因此我们对于按位考虑，对于第 $i$ 位，在遍历至 $a_j$ 时设 $sum_{a_j}$ 表示在它之后的与其互补的数的和，$cnt_{a_j}$ 表示与其互补的数的个数（此处互补的定义是与 $a_j$ 相加可以被 $2^i$ 整除，用 $^a_j$ 表示）。因此从后往前遍历即可得到 $f_i = \sum \limits_{j = 1}^n a_j \times cnt_{^a_j} + sum_{^*a_j}$。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

for (int i = 0;i <= 25;++i)
{
    int p = 1 << i;
    for (int j = n;j;--j)
    {
        ++cnt[a[j] % p];
        sum[a[j] % p] += a[j];
        f[i] += a[j] * cnt[(p - a[j] % p) % p] + sum[(p - a[j] % p) % p];
    }
    for (int j = 1;j <= n;++j) cnt[a[j] % p] = sum[a[j] % p] = 0;
}
for (int i = 0;i < 25;++i) ans += (f[i] - f[i + 1]) / (1 << i);