首先与等于零 相当于要求 每一位 在选的数里都有至少一个在该位为 0。直接求这个不太好求，我们考虑容斥：
设F(s) 为 不合法的位的集合至少是s的方案数 ，某一位不合法当且仅当选的数在这一位都是1。
于是答案就是Σ F(s) * (-1)^|s| ，因为在左边这个式子中，只有所有位都合法的选数集合会对答案贡献1 (相当于 C(0,0))；而只要有i个位置不合法(i>0)，那么它的贡献就是 杨辉三角 第i行 所有偶数列的和 - 所有奇数列的和，也就是0(noip常识啊233)。 [可以说 (-1)^i 是最基本的容斥系数了]。
所以现在问题的关键就是如何求F(s)。
发现F(s) = 2^num(s) - 1，其中 num(s) 表示a[i]的子集里有s的a[i]的个数。
然后就可以用刚刚那个博客的方法解决这个题了2333
#include<bits/stdc++.h>#define ll long longusing namespace std;const int ha=1000000007;const int maxn=1000000;int n,ci[30],CT[maxn+5],f[maxn+5],ans;inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}inline int ksm(int x,int y){ int an=1; for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; return an;}inline int read(){int x=0; char ch=getchar();for(;!isdigit(ch);ch=getchar());for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x;}inline void init(){ci[0]=1,CT[0]=1;for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;for(int i=1;i<=maxn;i++) CT[i]=CT[i^(i&-i)]^1;}inline void dp(){for(int i=0;i<20;i++)for(int j=maxn;j;j--) if(j&ci[i]) f[j^ci[i]]+=f[j];}inline void calc(){for(int i=0;i<=maxn;i++)if(CT[i]) ans=add(ans,add(ksm(2,f[i]),ha-1));else ans=add(ans,add(ha-ksm(2,f[i]),1));}int main(){init();while(scanf("%d",&n)==1){ans=0,memset(f,0,sizeof(f));for(int i=1;i<=n;i++) f[read()]++;dp(),calc();printf("%d\n",ans);}return 0;}
