看心情填坑

颓得一匹就来写一下这个题的题解。

鸣谢埃及小哥Ninjo

为了方便转换成所有数的or和为全集。

很容易想到DP，$dp_{i,j,k}$表示做到第i个数，前面的or和为j，后面的or和我们希望它是k的情况。但是直接DP的话复杂度太大了接受不了，所以我们把它子集差分一下，$ans_{i,j,k}=\sum_{l\epsilon k}dp_{i,j,l}$

然后就好了。

$dp_{i,j,k}->dp_{i+1,j,k}$

$dp_{i,j,k}->dp_{i+1,j,k \ and \ (not \ a[i])}$

还有一个不知道为什么TEX萎掉了，看代码吧

简单的容斥

#include<cstdio>
#define Rin register int
#define mo 1000000007
using namespace std;
inline int read(){
    int ret=0;char c=getchar();
    while((c<'0')||(c>'9'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
int dp[2][1024][1024];
int n,test;
int main(){
    n=read();
    dp[0][0][0]=1;
    for(Rin i=0;i<n;i++){
        Rin x=1023-read();
        for(Rin j=0;j<1024;j++)
            for(Rin k=j;;(--k)&=j){dp[i&1^1][j][k]=0;if(k==0)break;}
        for(Rin j=0;j<1024;j++)
            for(Rin k=j;;(--k)&=j){
                if(dp[i&1][j][k]){
                    dp[i&1^1][j][k]=(dp[i&1^1][j][k]+dp[i&1][j][k])%mo;
                    if((x&j)!=x){
                        dp[i&1^1][j|x][k^(k&x)]=(dp[i&1^1][j|x][k^(k&x)]+dp[i&1][j][k])%mo;
                        dp[i&1^1][j|x][(k^(k&x))|(x^(x&j))]=(dp[i&1^1][j|x][(k^(k&x))|(x^(x&j))]-dp[i&1][j][k])%mo;
                    }
                }
                if(!k)break;
            }
    }
    if(dp[n&1][1023][0]<0)dp[n&1][1023][0]+=mo;
    printf("%d",dp[n&1][1023][0]);
}

鼓哥帅啊