“蔚来杯“2022牛客暑期多校训练营4 补题题解（N）

---

觉得有帮助的点个赞！ [比赛地址](https://ac.nowcoder.com/acm/contest/33189) [参考的大佬题解](https://zhuanlan.zhihu.com/p/548121328)

N Particle Arts

比赛是想出思路了，但是竟然莫名其妙过不去，可能是因为1e5n的n三次方爆了，但是long long明明可以存下这么多，我不理解

#include<bits/stdc++.h>

using namespace std;

#define int long long 
#define db double

const int N = 1e5 + 10;

int n;
int a[N];
int cnt[20];  //记录第i位有几个1，从右往左排n~1 

int get_wei(int x){
    
	int res = 0;
	while(x){
    
		res ++ ;
		x >>= 1;
	}
	return res;
}

int get_er(int x, int y){
      //x这个数有y位二进制数 
	int res = 0;
	for(int i = 1; i <= y; i ++ ){
    
		if(x & 1){
    
			res ++ ;
			cnt[i] ++ ;
		} 
		x >>= 1; 
	}
	return res;
}

int tui(int iu){
      //填充1 
	int res = 0;
	for(int i = iu; i >= 1; i -- ){
    
		if(cnt[i]){
    
			res ++ ;
			cnt[i] -- ;
		}
		res <<= 1;
	}
	
	res >>= 1;

	return res;
}

int gcd(int a, int b){
    
	if(b) return gcd(b, a % b);
	else return a;
}

int li;  //记录1的个数 
int iu;  //最高位有几位 
int sum;  //计算数值和
int ans1, ans2;
int sut;

signed main()
{
    
	cin>>n;
	
	for(int i = 0; i < n; i ++ ){
    
		scanf("%lld", &a[i]);
		sum += a[i];
		int r = get_wei(a[i]);
		iu = max(iu, r);  //记录最高位数 
		li += get_er(a[i], r);  //累加1的个数 
	}
	//sum已记录 
	for(int i = 0; i < n; i ++ ){
      //填充n个数
		int t = tui(iu);
		ans1 += t * t;
		sut += sum * t;
	}
	
	ans1 *= n;
	ans1 += sum * sum;
	ans1 -= 2 * sut;
	
	ans2 = n * n;
	
	int ou = gcd(ans1, ans2);

	if(ou > 1){
    
		ans1 /= ou;
		ans2 /= ou;
	}
	
	//最小公倍数*最大公约数=a*b 
	//最小公倍数=ans1*n/最大公约数
    
	if(ans1 == 0) cout<<"0/1"<<endl;
	else cout<<ans1<<"/"<<ans2<<endl;
	
	return 0;
}