ABC 384 F
abc 经典 EF 出式子题。
问题陈述
对于正整数 \(x\) ，定义 \(f(x)\) 如下："当 \(x\) 是偶数时，继续除以 \(2\) 。经过这些除法后， \(x\) 的最终值为 \(f(x)\) "。例如， \(f(4)=f(2)=f(1)=1\) 和 \(f(12)=f(6)=f(3)=3\) 。
已知长度为 \(N\) 的整数序列 \(A=(A_1,A_2,\ldots,A_N)\) ，求 \(\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(A_i+A_j)\) 。
做法
首先原式可以转化为算 \(\displaystyle \sum_{i=1}^N \sum_{j=1}^N f(A_i+A_j)\) ，然后再算 \(\displaystyle \sum_{i=1}^N f(A_i+A_i)\)。
这是个经典的trick。
然后这个式子不是很好算贡献。
我们将其写为：\(\displaystyle \sum_{i=1}^N \sum_{j=1}^N \frac{a_i+a_j}{2^k}\)
其中 \(k\) 是 \(a_i+a_j\) 的因数中最大二次幂的幂次，也就是 \(lowbit(a_i + a_j) = 2^k\)。
将 \(k\) 提到前面算贡献
\[\sum ^{25}_{k=1} \frac{1}{2^k}( \sum _{i=1}^n \sum _{j=1}^n (a_i+a_j)*[lowbit(a_i+a_j) = 2^k]) \]设 \(ans_i\) 表示满足 \(lowbit(a_i + a_j) = 2^i\) ，的所有配对 \((a_i,a_j)\) 的和。
原式等于
\[\sum ^{25}_{k=1} \frac{1}{2^k}ans_k \]考虑如何计算 \(ans_i\)。
我们可以先计算一个 \(f_i\) ，表示所有 \((a_i + a_j) \mod 2^i = 0\) 的 \((a_i+a_j)\) 的和。
这个非常好算，\(O(n \log V)\) 即可算出。
具体来说，枚举 \(i = [0,25]\)，令 \(a_i\mod 2^i \rightarrow a_i\)，拿一个桶记一下就做完了。
然后我们发现 \(ans_i = f_i -f_{i+1}\)。
证明也是显然的。
在所有因数含有 \(2^i\) 次方的集合中，除去能整除 \(2^{i+1}\) 的，则剩下的便刚好是 \(lowbit(a_i+a_j)=2^i\) 的了。
于是就做完了。
// Problem: F - Double Sum 2
// Contest: AtCoder - Toyota Programming Contest 2024#12（AtCoder Beginner Contest 384）
// URL: https://atcoder.jp/contests/abc384/tasks/abc384_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// Author: Eason
// Date:2024-12-14 20:34:44
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5,M = 5e7 +5;
int pw2[30];
int n;
int a[N];
int sum[30];
int cnt[M];
int ct[M];
int tp[N];
void solve()
{
cin >> n;
rep(i,1,n) tp[i] = a[i] = rd();
for (int i = 25;i >= 0;i--)
{
int mm = (1<<i);
rep(i,0,mm) cnt[i] = ct[i] = 0;
for (int i =1;i <= n;i++) a[i] = tp[i] % mm,cnt[a[i]]+=tp[i],ct[a[i]]++;
for (int j = 1;j < mm;j++)
{
if (ct[j] && ct[mm-j])
sum[i] += cnt[j]*ct[mm-j] + ct[j]*cnt[mm-j];
}
if (ct[0])
sum[i] += cnt[0] *ct[0]*2;
}
int ans = 0;
for (int i = 25;i >= 0;i--)
{
ans += (sum[i]-sum[i+1])/(1<<i);
}
int S = 0;
for (int i = 1;i <= n;i++)
{
int cnt = 0;
int x = tp[i];
while (x %2 == 0) cnt++,x/=2;
ans -= x;
S += x;
}
ans /=2;
ans += S;
cout << ans << endl;
}
signed main()
{
int t;t = 1;
while(t--)
{
solve();
}
return 0;
}