自动搬运

查看原文

来自洛谷，原作者为

	Chx Today is a present

搬运于2025-08-24 22:54:49，当前版本为作者最后更新于2024-01-04 18:31:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给出一个长度为 $n$ 的序列 $d$，求：

$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))} $$

其中定义 $\oplus$ 代表二进制下两数相加所得到的 $1$ 的个数， $\otimes$ 代表二进制下较大的减较小的所得到的 $1$ 的个数。

我们发现当确定了 $\sum\limits d_i$ 后，种类数的量级也会被确定下来：当我们的序列形如 $0,1,2,3,4,5 \dots x$ 时，$d_i$ 的种类是最多的，但发现这个 $x$ 并不会很大，设 $s=\sum\limits d_i$，那么这个 $x$ 最多在 $\sqrt {s}$ 的量级，所以直接统计每种 $d_i$ 的数量暴力计算即可。

我们用 $V$ 表示值域上界，那么时间复杂度是 $O(s \log V)$ 的，预处理 $\operatorname{popcount}$ 可以做到 $O(s)$，题解给出的是 $O(s \log V)$ 的解法。

$Code$

#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
template<typename T>inline void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;
}
int n,cnt[N],d,a[N],len;
long long ans;
inline int calc(int x){
    int res=0;
    while(x) ++res,x-=x&-x;
    return res;
}
int main(){
    read(n);
    while(n--){
        read(d);
        if(cnt[d]++==0) a[++len]=d;
    }
    for(int i=1;i<=len;++i)
        for(int j=1;j<=len;++j)
            ans+=1ll*cnt[a[i]]*cnt[a[j]]*(calc(a[i]+a[j])+calc(abs(a[i]-a[j])));
    printf("%lld",ans);
    return 0;
}