自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:17:26，当前版本为作者最后更新于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;
}