题解 P6102 【谔运算】
引领天下
2020-02-15 18:23:52
首先，这个题是肯定不能按题意模拟的。$ O(n^4) $ 的复杂度，我们绝对承受不起。
那么既然涉及的是位运算，我们就考虑将输入的 $a$ 进行二进制拆分，对每一位进行考虑。
考虑每位出现什么样的数对答案有贡献：
- ( $ a_i=0 $ | $ a_j=0 $ ) ^ ( $ a_k=1 $ & $ a_l=1 $ )
- ( $ a_i=1 $ | $ a_j=0 $ ) ^ ( $ a_k=0 $ & $ a_l=0 $ )
（以上并没有考虑顺序）
那么对于每一位，只有两种情况下该位的四个数对答案有贡献。我们只需统计每位上 $ 0 $ 和 $ 1 $ 的个数，然后用容斥原理计算即可。
代码：
```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))
using namespace std;
int n;
__int128 ans,s,a[500005],x,y;
const __int128 mod=(__int128)4294967296;//定义模数
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(__int128 &x){
int f=1;x=0;char ch=nc();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
x*=f;
}
inline void write(__int128 n){//由于我用的int128，所以必须要自己写一个输入输出
if (n==0)return ;
write(n/10);
putchar(n%10+'0');
}
int main(){
scanf("%d",&n);
register int i,j;
for (i=1;i<=n;i++)read(a[i]);
for (i=1;i<33;i++){
x=y=0;
for (j=1;j<=n;j++)if((1ll<<i-1)&a[j])x++;else y++;//确定第 i 位上 0 和 1 的个数，由于 1<<i-1 的结果是 1 后面一串 0 的形式，所以可以直接放心 &
s=((x+y)*(x+y)%mod-y*y%mod)*((x+y)*(x+y)%mod-x*x%mod)+(((((x*x)%mod)*y)%mod)*y)%mod;//分别对应上面讨论的两种情况
ans=(ans+s*(1ll<<i-1))%mod;//利用容斥原理统计贡献，并加到答案里。
}
ans=(ans+mod)%mod;//巨坑！这里必须加个 mod ，要不然会导致输出负数……
if(ans)write(ans);
else putchar('0');
return 0;
}
```