题意

定义函数 $f(X) $： $x$ 为偶数则除以 $2$ ，一直除到为奇数时停止，这个奇数就是函数值。
现给定一个 $n$ 个数字的数组 $A$ 。求$$\sum_{i=1}^N \sum_{j=i}^N f(A_i + A_j)$$

思路

这是个推式子题，全程都是做各种变换以及将其代码实现，对于本人来说还是有点难度的。

首先对于原式可以拆分为
$$\sum_{i=1}^N \sum_{j=i}^N f(A_i + A_j) = \sum_{i=1}^N \sum_{j=i+1}^N f(A_i + A_j) + \sum_{i=1}^n f(A_i + A_i)$$
两部分，其中后者非常好算，直接一次循环按照题意模拟即可求出贡献。

前者则需要推柿子。
函数 $f(A_i+A_j)$ 的操作是将参数中所有的因子2都除掉
则可以写成

$$ \sum_{i=1}^N \sum_{j=i+1}^N \frac{a_i+a_j}{2^k}$$

其中 $k$ 是 $a_i+a_j$ 的因子中最大二次幂的幂次，即$lowbit(a_i + a_j) = 2^k$
将 $k$ 提出来，分别计算每个$k$ 的贡献
$$\sum_{k=0}^{24} \frac{1}{2^k}[\sum_{i=1}^N \sum_{j=i+1}^N {(a_i+a_j)} * (lowbit(a_i + a_j)==2^k)]$$

设$ans_i$表示满足条件$lowbit(a_i+a_j)=2^i$
，的所有配对 $(ai,aj)$ 的和

原式等于
$$\sum_{k=0}^{24} \frac{1}{2^k}ans_k$$

考虑如何计算 $ans_i$
先计算一个 $f_i$ ，表示所有 $(a_i+a_j) \mod 2^i = 0$ 的 $(a_i+a_j)$ 的和

$f_i$ 的计算方式：

1. $(a_i + a_j) \mod 2^k$ 这一条件等价于 $a_j \equiv -a_i \mod 2^k$
2. 使用桶数组记录 $a_j$ 将 $-a_i \mod 2^k$ 丢进去计算就行。

这里的操作不懂可以看看我之前整理的这类题目 https://www.acwing.com/blog/content/56820/

那么 $ans_i = f_i - f_{i + 1}$
这是因为 $f_i$ 是所有满足能整除$2^i$ 这个条件的 $a_i + a_j$ 的和。要求的 $ans_i$ 不能有多余的2作为因子

简单来说
$f_i$ 包含 $a_i+a_j$ 是 {$2^i, 2^{i+1}, 2^{i+2}…$} 任意某个数的倍数。
$ans_i$ 包含 $a_i+a_j$ 只能是$2^i$ 的倍数，不能是 $2^{i+1}, 2^{i+2}…$ 的倍数

那么 $f_i$ 包含 $f_{i+1}$ ，多出了$2^i$ 的倍数这部分。
这个求解思想类似于后缀和。
这样就求完了

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

const int N = 2e7 + 10, M = 25;

int n;
int a[N], cnt[N]; // cnt[i]:余数为i的个数，d[i]:余数为i的 a[j]的和
LL d[N], f[M + 1]; // f[k]：(ai + aj) % 2^k == 0 的和 

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);

    for(int j = 0; j < M; j ++) //求出f[j]
    {
        for(int i = 0; i < N; i ++) d[i] = cnt[i] = 0;//初始化
        int mod = (1 << j); // 模数
        for(int i = n; i; i --) // 看题意，倒着求
        {
            int t = (-a[i] % mod + mod) % mod;
            f[j] += cnt[t] * (LL)a[i] + d[t]; //求(ai+aj)的和：前者符合条件的aj的数量*ai，加上后者所有符合条件aj的和

            //维护cnt和d
            cnt[a[i] % mod] ++;
            d[a[i] % mod] += a[i];
        }
    }

    LL ans = 0;
    for(int i = 0; i < M; i ++)
        ans += (f[i] - f[i + 1]) / (1 << i); //计算ans

    //单独计算自己和自己
    for(int i = 1; i <= n; i ++)
    {
        int x = a[i];
        while(x % 2 == 0)
            x /= 2;
        ans += x;
    }
    cout << ans << "\n";
}

int main()
{
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}

细节

1. $M$ 为 $log2(1e7)$ 上取整
2. 求 $f$ 时需要用两个桶数组，分别记录数量以及 $sum$.
3. 每个 $k$ 是独立计算的

学习参考：https://www.cnblogs.com/codwarm/p/18607348