牛客多校4 N Particle Arts

输入

5
1 2 3 4 5

输出

54/5

题目大意：给我们n个小球，每个小球都有一个值，每个小球随机碰撞，碰撞后两个小球消失，然后会新产生两个小球，新产生的两个小球的值分别为原来两个小球的值的或和与，问当经过无限次的碰撞后方差会稳定在一个值，问这个值是多少。

解题思路：首先我们发现，两个球碰撞后新产生的两个值和原来的两个值相比，每一位上1的总个数是不变的，所以说在小球互相碰撞的过程中，这n个数所有位上的1的个数始终保持不变，那么最终到什么时候方差不会再改变了呢？从公式出发，因为每一位上1的个数保持不变，所以所有这n个数的平均数保持不变，那么要使方差不变，就要使所有数碰撞后产生的新数和原来的数保持一致，当一个数a二进制是1的位置是另一个数b二进制1的位置的子集时，a|b=b,a&b=a，所以我们可以统计每一位上1的数量，让这些1都尽可能集中在一个数上，然后可以构造出最后方差稳定后的序列，然后直接套用公式求解即可。这里需要注意的是，对于方差的公式不能直接使用，直接用会爆long long，所以需要进行化简，比赛的时候就因为没有化简直接wa麻了。方差化简后的结果如下：

 上代码：

#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+10;
long long n,a[N],b[20],ans[N],t[20];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=0;j<=15;j++)
		{
			t[j]+=((a[i]>>j)&1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=15;j++)
		{
			if(t[j])
			{
				ans[i]|=(1<
				t[j]--;
			}
		}
	}
    long long u=0,u2=0;
    for(int i=1;i<=n;i++)
    {
    	u+=ans[i];
    	u2+=ans[i]*ans[i];
	}
	long long zi=n*u2-u*u;
	long long mu=n*n;
	long long g=__gcd(zi,mu);
	zi/=g;
	mu/=g;
	cout<"/"<
	return 0;
 }