首先暴力相与是过不去的(即便是优化的也不过去,因为1s大概只能执行9位数的循环,而1e5*1e5要10位数了)。
int main(){ scanf("%lld",&n); ll t=n; while(n--){ scanf("%lld",&i); for(int j=0;j<vec.size();j++){ sum+=i&vec[j]; }tsum+=i&i; vec.push_back(i); } cout<<2*sum+tsum<<endl; return 0; }
观察规律(以例子为例)
001(1)
010(2)
011(3)
100(4)
101(5)
每个数要分别与其他的数相与一次(包括自己),然后把结果相加。
只有两种情况:1&1=1,0&1=0;
相当于每一位分别与每一位相与然后再相加。
以末位为例,1&1,1&0,1&1,1&0,1&1相加等于3。因为某位一共有三个1,只有1和1相与才会有结果。
以上是(1)的情况。(3),(5)也是某位为1.所以结果为3^2;
这样把每一位都算出来就可以了。
最后算出来的都是每一位的二进制数。然后用快速幂求10进制数就可以了。
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<map> #include<cstring> using namespace std; typedef long long ll; ll n,i,a[10000]; ll sum=0,tsum=0,res=0; ll fastpow(int a,int b){//快速幂 ll res=1; while(b){ if(b&1)res*=a; a*=a; b>>=1; } return res; } int main(){ memset(a,0,sizeof(a)); scanf("%lld",&n); while(n--){ tsum=0; scanf("%lld",&i); while(i){//算每一个数的位是否为1,统计个数。 if(i&1)a[tsum]++; tsum++ i>>=1; } sum=max(sum,tsum); } for(int i=0;i<sum;i++){ res+=a[i]*a[i]*fastpow(2,i);//二进制-->十进制 } cout<<res<<endl; return 0; }