题解 | #N Particle Arts#

N Particle Arts

无限碰撞之后，每一位的1和0都会分成两边，此时任意两个数字碰撞都会有 。(证明请找出题人)

重构一下数组，也就是按顺序把每一位的1尽可能丢进一个数字里，那么可以保证，先得到的数字跟后得到的数字之间一定可以满足 。

例如，样例中，{1,2,3,4,5}转成2进制即{001,010,011,100,101}，重构后为{111,111,001,000,000}，任意两个数字碰撞都将不再改变数组。

之后计算这个数组的方差，可以把式子展开，就只需要整数计算，可以直接开long long存，最后再gcd一下即可。

$sum={\sum }_1^n{a}_{i}sum\; =\; \backslash sum\_1^n\; a\_i$

$\mu =\frac{sum}{n}\backslash mu\; =\; \backslash frac\{sum\}\{n\}$

$(x_i-\mu {)}^2=x_i^2-2x_i\mu +{\mu }^2(x\_i\; -\; \backslash mu)^2\; =\; x\_i^2\; -\; 2\; x\_i\; \backslash mu\; +\; \backslash mu\; ^2$ （完全平方公式展开）

$\frac{a}{b}={\sum }_1^n{x}_i^2+n\times \frac{su{m}^2}{n^2}-{\sum }_1^{n}2\times x_i\times \frac{sum}{n}\backslash frac\{a\}\{b\}\; =\; \backslash sum\_1^n\; x\_i^2\; +\; n\; \backslash times\; \backslash frac\{sum^2\}\{n^2\}\; -\; \backslash sum\_1^n\; 2\; \backslash times\; x\_i\; \backslash times\; \backslash frac\{sum\}\{n\}$

$a={\sum }_1^{n}n\times x_i^2+su{m}^2-{\sum }_1^{n}2\times x_i\times suma=\backslash sum\_1^n\; n\; \backslash times\; x\_i^2\; +sum^2\; -\; \backslash sum\_1^n\; 2\; \backslash times\; x\_i\; \backslash times\; sum$ （对 $x_i^{2}x\_i^2$ 部分通分）

$b=nb=n$

${\sigma }^2=\frac{a}{b}\times \frac{1}{n}\backslash sigma^2\; =\; \backslash frac\{a\}\{b\}\; \backslash times\; \backslash frac\{1\}\{n\}$

此时，所有计算都为整数计算，并且在long long范围内，最后对 $aa$ 和 $n^{2}n^2$ 约分即可。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

void solve(){
	LL n;
	cin>>n;
	vector<LL> a(n+1);
	vector<int> b(20);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=0;j<20;j++){
			if(a[i]&(1<<j)) b[j]++;
		}
	}
	LL sum=0;
	for(int i=1;i<=n;i++){
		a[i]=0;
		for(int j=0;j<20;j++){
			if(b[j]){
				b[j]--;
				a[i]+=1<<j;
			}
		}
		sum+=a[i];
	}
	LL ans=0,sub=0;
	for(int i=1;i<=n;i++){
		ans+=a[i]*a[i];
		sub+=a[i]*sum;
	}
	ans*=n;
	ans+=sum*sum;
	ans-=2*sub;
	if(ans==0){
		cout<<"0/1"<<endl;
		return;
	}
    n*=n;
	int g=gcd(ans,n);
	ans/=g;
	n/=g;
	cout<<ans<<"/"<<n<<endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}
/*
*/