对于组合数的奇偶性：

根据卢卡斯定理，相当于是在p进制下的分解，对于每一C(n,m)，如果n，m不同，那组合数就是偶数

所以组合数C(n,m)为奇数当且仅当 n&m==m

然后就是dp了

设f[i]为以i结尾的方案数

枚举i的子集j，如果j的位置在i的后面且i&j==j，则更新

答案就是所有f[a[i]]的和

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int maxn = 255555;const int mod = 1e9+7;int n,m,up,ans;int a[maxn],c[maxn];int f[maxn]; // 以i为结尾 ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}int main(){ n=read(); for(int i=1;i<=n;++i) a[i]=read(),c[a[i]]=i,up=max(up,a[i]),f[a[i]]=1; for(int i=1;i<=n;++i){ for(int j=(a[i]-1)&a[i];j;j=(j-1)&a[i]){ // 枚举子集 if(c[j]>i){ if((a[i]&j)==j) f[j]=(f[j]+f[a[i]])%mod; } } } for(int i=1;i<=n;i++){ ans=(ans+f[a[i]]-1)%mod; } printf("%d\n",ans); return 0;}