https://atcoder.jp/contests/abc384/tasks/abc384_f

Problem Statement

For a positive integer $x$, define $f(x)$ as follows: “While $x$ is even, keep dividing it by $2$. The final value of $x$ after these divisions is $f(x)$.” For example, $f(4)=f(2)=f(1)=1$, and $f(12)=f(6)=f(3)=3$.

Given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$, find $\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(A_i+A_j)$.

对于一个$A_i+A_j$，我们确定它的f值，是找到最大的k，使得$$(A_i+A_j)\%2^k==0,f(A_i+A_j)=(A_i+A_j)/2^k$$
所以，对于一个i，我们找i位置之前所有与$A_i$相加能模$2^k$为0的$A_j$，则可以快速计算出它们对答案的贡献$C*A_i+S$。
其中C是这样的$j$的个数，S是满足条件的$j$位置上的$A_j$的和。注意这里的k是最大的k使得$(A_i+A_j)\%2^k==0$。
因此我们容易想到，一个map存储之前出现过的$(A_i\%2^k)$的值，然后当需要计算答案时，则需要查询map中值为$-A_i\%2^k$的个数和累加。这样可以计算出答案。
因此我们按照上述方法，对每个k都求一下满足$(A_i+A_j)%2^k==0$的所有$A_i+A_j$的和，然后除以2^k即可。

到这里问题基本解决，但是有一个小bug，如果我们按时找上文方法存储$(A_i\%2^k)$的值，注意这里的k不能保证是最大的，也就是说对一个k求完之后，实际得到的是所有$(A_i+A_j)\%2^{k1}==0,k1 \geqslant k $的和。
因此我们还需要转变为恰好为k的和，实际上很简单，只需要减去$(A_i+A_j)\%2^{k1}==0,k1 \geqslant k+1 $这部分的和即可。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
ll qmi(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a;
        a = a*a;
        b >>= 1;
    }
    return res;
}

void solve(){
    ll n;cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    ll ans = 0;
    int K = 25;
    vector<ll> cur(30);
    for(int i=0;i<=K;i++){
        map<ll,pll> mp;
        ll kk = 1<<i;
        for(auto x:a){
            auto &[c1,s1] = mp[x%kk];
            c1++,s1+=x;         
            auto &[c2,s2] = mp[(-(x%kk)+kk)%kk];
            cur[i] += s2 + c2*x;    
        }
    }
    for(int i=0;i<=K;i++){
        ans += (cur[i]-cur[i+1])>>i;
    }
    cout<<ans<<endl;
}

int main(){     
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}