牛客练习赛60a大吉大利,二进制+组合

大吉大利

http://www.nowcoder.com/questionTerminal/02de3728585142b0b25da375fd00cdc4

把所有的数转成二进制,然后统计每一位1的个数,然后每一位内部组合,注意组合a&b==b&a且视为2组
最后再加上每个数自己和自己组合,即累和
如1,10,11,100,101(1-5),20位累计3(C(3,2)*2*20),21位累计2(C(2,2)*2*21),22累计2(C(2,2)*2*22,这里是18
最后加上1到5的和是15,得出33
#include<bits/stdc++.h>

using namespace std;
const int N=1e5+10;
typedef long long ll;

ll fct[N];
ll a,d,n,dig[40],ans,sum;

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	fct[0]=1, fct[1]=1;
	for(int i=2;i<n;i++){
		fct[i]=fct[i-1]*i;
	}
	for(int i=0;i<n;i++){
		cin>>a;
		sum+=a;
		d=0;
		while(a){
			if(a&1) dig[d]++;
			a>>=1;
			d++;
		}	
	} 
	for(int i=0;i<32;i++){
		if(dig[i]>=2)ans+=fct[dig[i]]/fct[dig[i]-2]*(1<<i);
	}
	cout<<ans+sum<<endl;
	return 0;
}

创作不易,(你懂的)
全部评论

相关推荐

totoroyyw:千年老妖😂
投递华为等公司10个岗位
点赞 评论 收藏
分享
4 收藏 评论
分享
牛客网
牛客企业服务