题解 P6102 【[EER2]谔运算】

StudyingFather · 2020-02-18 16:42:58 · 题解

UPD（2020/5/11）：修了之前 x,y 打反的锅。

因为每一位对答案的贡献是独立的，所以我们把每一位分开考虑。

现在问题变成了：给出一个 01 串，求题目中式子的值。

显然，只有以下两种情况会对答案产生 1 的贡献：

• and 值为 1 的二元组 (i,j) 和 or 值为 0 的二元组 (k,l)；
• and 值为 0 的二元组 (i,j) 和 or 值为 1 的二元组 (k,l)；

本题对二元组没有任何限制，因此这四个二元组的数量都很好计算。

设这个 01 串中有 x 个 0，y 个 1，则：

• and 值为 1 的二元组有 y^2 个；
• or 值为 0 的二元组有 x^2 个；
• 剩下的数据都可以取补得到，这里不再赘述。

#include <iostream>
using namespace std;
unsigned t[35];
int main()
{
 ios::sync_with_stdio(false);
 unsigned n,tot,ans=0;
 cin>>n;
 tot=n*n;
 for(int i=1;i<=n;i++)
 {
  unsigned x;
  cin>>x;
  for(int j=0;j<=31;j++)
   if((x>>j)&1)t[j]++;
 }
 for(int i=0;i<=31;i++)
 {
  unsigned andn=t[i]*t[i],orn=(n-t[i])*(n-t[i]);
  ans+=(andn*orn+(tot-andn)*(tot-orn))<<i;
 }
 cout<<ans<<endl;
 return 0;
}