BNU1065：简单的问题(数位dp)
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int dp[10005][17];int sum[17];int set(int n){ int i,ans = 1; if(n == 0) return 1; for(i = 1; i<=n; i++) ans*=2; return ans;}int main(){ int n,a[10001]; int T; int i,j,k,t,r; int ans; scanf("%d",&T); while(T--) { scanf("%d",&n); ans=0; memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); for(i=0; i<n; ++i) { scanf("%d",&a[i]); t = a[i]; for(j = 0; j<=16; j++) { r = t%2; if(r) { sum[j]++;//第j位1的总个数 dp[i][j]=1;//该数的第j位2进制是1 } t/=2; } } for(i = 0; i<n; i++) { for(j = 0; j<=16; j++) { if(dp[i][j])//现在此位是1，与任何其他数相或都必为1，所以是总数加这位化为十进制的值 ans+=n*set(j); else//该位是0，则将其他数字同位为1的个数相加 ans+=sum[j]*set(j); } } printf("%d\n",ans); } return 0;}
