题目链接：见这里
题意：给出n个非负的整数a[i]，求选出至少一个数使得这些数按位与的结果为0的方案数。1 <= n <= 10^6，0<=a[i]<=10^6 。输出答案对1e9+7取模
解题思路，来自Wanafly每日一题。
原问题等价于给定n个包含于{0,1,2,…,19}的集合，求选出若干个集合使得它们的交为空的方案数，
直接不太好做，考虑容斥，记g[S]为选出若干个集合使得它们的交包含S的方案数，
那么有g[S]=2^f[S]-1，其中f[S]表示包含S的集合的个数，这是因为任意多个包含S的集合之交仍然包含S，
记cnt[S]表示S的个数，那么f[S]=sum cnt[T]，这里对所有包含S的T求和，这就是高维前缀和（请读者回忆一下SPOJ TLE），
那么可以求出所有g[S]，再容斥一下即可求出交集恰好为空的方案数，或者也可以做一次高维差分，
复杂度O(n+s*2^s)，这里s=20。ORZ，劲啊。

代码如下： 注意不用long long 的时候，快速幂小心爆long long 。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int pow(int a, int n){
    int res = 1;
    while(n){
        if(n&1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return res;
}
void solve(int f[], int n, int ty){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (1<<n); j++){
            if(j & (1<<i)) continue; //非空集不算
            if((f[j|(1<<i)] += ty * f[j]) >= mod) f[j|(1<<i)] -= mod;
            if((f[j|(1<<i)]) < 0) f[j|(1<<i)] += mod;
        }
    }
}
int f[1<<20];
int main()
{
    int n;
    scanf("%d", &n);
    int mask = (1 << 20) - 1;
    for(int i = 0; i < n; i++){
        int x;
        scanf("%d", &x);
        f[x^mask]++;
    }
    solve(f, 20, 1);
    //处理g
    for(int i = 0; i < (1<<20); i++){
        f[i] = pow(2, f[i]);
    }
    //f等价于g了
    solve(f, 20, -1); //容斥
    printf("%d\n", f[mask]);
    return 0;
}