[CTSC2017] 吉夫特

由lucas定理，c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)可知c(n,m)为奇数的充要条件是(n&m)=m。

考虑到ai<=233333，可以开桶优化dp（笑。这样的总转移次数=σi的子集数=3^log2。

#include <bits/stdc++.h>
using namespace std;
const int n=233335;
const int mod=1000000007;

int n,a[n],p[n],f[n];

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) {
        scanf("%d",a+i);
        f[a[i]]=1;
        p[a[i]]=i;
    }
    for(int i=1; i<=n; ++i) {
        for(int j=a[i]; j; j=(j-1)&a[i]) {
            if(p[j]>i) (f[j]+=f[a[i]])%=mod;
        }
    }
    int s=0;
    for(int i=1; i<=n; ++i) (s+=f[a[i]]-1)%=mod;
    printf("%d\n",(s+mod)%mod);
    return 0;
}