（2022牛客多校四）N-Particle Arts（思维）

题目：

样例输入： 

5
1 2 3 4 5

样例输出：

54/5

题意：

n个粒子，每个粒子有一个能量ai。两两随机碰撞，假如两个例子的能量分别为a和b，那么碰撞一次两粒子的能量分别变为a&b,a|b。求所有粒子能量稳定后的方差。

我们分析两个粒子碰撞后的结果可以发现，对于a和b的二进制位，假如第i位两者都是1，那么碰撞后形成的两个粒子能量的第i位都是1，如果第i位两者都是0，那么碰撞后形成的两个粒子能量的第i位都是0，如果碰撞前a粒子和b粒子能量第i位一个是1一个是0，那么碰撞后形成的粒子第i位也是一个1一个0，但是1是在或运算后的那个粒子上，那么容易发现，每次碰撞都会使得一个粒子的能量变大（也可能不变），而且碰撞后二进制位上1的个数不变，只是有可能从1个粒子转移到另一个粒子上，由于碰撞了无数次，那么肯定使得二进制上的1尽可能地集中在了少数上，最后的稳定态也就是对于任意的i和j，都有（ai|aj,ai&aj）=(ai,aj)或者 （ai|aj,ai&aj）=(aj,ai) 。 所以我们只需要统计一开始给定的n个数中每一位上1出现的次数即可，最后对n个数进行分配，每次都尽可能把1分配在一个数上，最后求一下期望即可。

需要注意的一点就是由于数比较大，所以可能会爆long long，所以建议直接用__int128计算。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int cnt[200];
long long a[N],b[N];
int main()
{
	long long n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%lld",&a[i]);
		for(int j=0;j<15;j++)
			cnt[j]+=(a[i]>>j&1);
	} 
	__int128 ans=0,ans1=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<15;j++)
		if(cnt[j])
		{
			b[i]|=(1<<j);
			cnt[j]--;
		}
		ans+=b[i];
		ans1+=b[i]*b[i];
	}
	__int128 anss=ans1*n+ans*ans-2*ans*ans;
	__int128 t=__gcd(anss,(__int128)n*n);
	long long up = anss/t;
	long long down = n*n/t;
	printf("%lld/%lld",up,down); 
	return 0;
}