[LMXOI Round 1] Size 题解

__Chx__ · 2024-01-04 18:31:31 · 题解

题意

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

其中定义 \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;
}