Codeforces119 D. Jzzhu and Numbers（容斥+Sosdp）

题意：

给出n个数,问有多少个子集,满足它们的与起来等于0

数据范围：n<=1e6，a(i)<=1e6

解法：

容斥:
答案=所有方案-至少1位为1的方案+至少2位为1的方案-至少3位为1的方案...至少i位为1的方案可以改一下:
d[i]表示状态至少为i的所有状态的数量(在本题是x&i=i的x的数量),用Sosdp可以计算出来
方案数为d[i]^2-1,减一是减掉空集
最后对于每个状态i,统计二进制位数,根据位数进行上面的容斥就行了
"计算状态至少为i的方案数+统计二进制位容斥"和"至少i位为1进行容斥"的结果是一样的ps:
子集:1的位置可以是0
超集:0的位置可以是1参考:
1.本题做法
https://www.cnblogs.com/zwfymqz/archive/2018/11/06/9915979.html
2.高维前缀和(Sosdp)
https://www.cnblogs.com/heyuhhh/p/11585358.html

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e6+5;
const int mod=1e9+7;
int p[maxm];
int d[maxm];
int a[maxm];
int n;
int cal(int x){int ans=0;while(x){x&=(x-1);ans++;}return ans;
}
signed main(){//预处理pow(2,n)p[0]=1;for(int i=1;i<maxm;i++){p[i]=p[i-1]*2%mod;}//scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);d[a[i]]++;}for(int i=0;i<20;i++){//Sosdp,枚举每一位for(int j=(1<<20)-1;j>=0;j--){if(!(j>>i&1)){//超集d[j]+=d[j|(1<<i)];}}}for(int i=0;i<(1<<20);i++){//数的个数为d[i],方案数为pow(2,d[i])-1,减1是因为不能为空集d[i]=p[d[i]]-1;}int ans=0;for(int i=0;i<(1<<20);i++){int t=cal(i)%2?-1:1;ans=(ans+t*d[i])%mod;}ans=(ans%mod+mod)%mod;printf("%d\n",ans);return 0;
}