看懂题目，很容易想到容斥原理。
刚开始我用的是二进制表示法实现容斥原理，但是一直超时。后来改为dfs就过了……
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define MAX 50000 11 using namespace std; 12 ll an[16],ans; 13 int n; 14 int get(ll n) 15 { 16 int t=0; 17 while(n){ 18 n-=(n&-n); 19 t++; 20 } 21 return t; 22 } 23 void dfs(int i,ll sum,ll k) 24 { 25 ans+=(1ll<<(get(sum)))*k; 26 for(int j=i+1;j<n;j++) 27 dfs(j,sum&an[j],-2*k); 28 } 29 ll solve(int n) 30 { 31 ll ans=0,res,m=1; 32 int i,j,temp; 33 for(i=1;i<(1<<n);i++){ 34 temp=0; 35 for(j=0;j<n;j++){ 36 if(i&(1<<j)){ 37 temp++; 38 if(temp==1) res = an[j]; 39 else res=res&an[j]; 40 } 41 } 42 res=(1<<get(res)); 43 ans+=m*res; 44 m*=-2; 45 } 46 return ans; 47 } 48 int main(){ 49 int i,t,k=1; 50 scanf("%d",&t); 51 while(t--){ 52 scanf("%d",&n); 53 for(i=0;i<n;i++) 54 scanf("%I64d",&an[i]); 55 ans=0; 56 for(i=0;i<n;i++) 57 dfs(i,an[i],1); 58 printf("Case #%d: %I64d ",k++,ans); 59 } 60 return 0; 61 }