HDU 4901. The Romantic Hero

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=4901

題意

給定n個數字,從n個數字鐘選出來m個(1<m<=n),分成兩個集合
每個集合非空,要求第一個集合中的數字的下標都要小于第二個集合
而且第一個集合的異或和(^)等於第二個集合的與(&)和 求方法數,對1000000007取餘

解法

動態規劃解法
f[i][j]表示處理前i個數字異或和(^)等於j的方法數
g[i][j]表示從後往前處理,處理到i,數字與和(&)等於j的方法數
g1[i][j]表示從後往前處理,處理到i,而且i位置的數字被選中了,數字與和(&)等於j的方法數
最後只需要枚舉i和j,然後對f[i][j]*g1[i+1][j]求和就是答案

const int N=1024*2;
const int M=1005;
const int mod=1000000007;
int f[M][N],g[M][N],g1[M][N];
int a[M];
void init() {
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    memset(g1,0,sizeof(g1));
}
void solve() {
    init();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    f[1][a[1]]=1;
    for(int i=2;i<=n;i++) {
        f[i][a[i]]++;
        for(int j=0;j<N;j++) {
            if(f[i-1][j]) {
                f[i][j]+=f[i-1][j];
                f[i][j]%=mod;
                int tmp=j^a[i];
                f[i][tmp]+=f[i-1][j];
                f[i][tmp]%=mod;
            }
        }
    }
    g[n][a[n]]=1;
    g1[n][a[n]]=1;
    for(int i=n-1;i>0;i--) {
        g[i][a[i]]++;
        g1[i][a[i]]++;
        for(int j=0;j<N;j++) {
            if(g[i+1][j]) {
                g[i][j]+=g[i+1][j];
                g[i][j]%=mod;
                int tmp=j&a[i];
                g[i][tmp]+=g[i+1][j];
                g[i][tmp]%=mod;
                g1[i][tmp]+=g[i+1][j];
                g1[i][tmp]%=mod;
            }
        }
    }
    LL ans=0;
    for(int i=1;i<n;i++) {
        for(int j=0;j<N;j++) {
            ans+=((LL)f[i][j])*((LL)g1[i+1][j]);
            ans%=mod;
        }
    }
    printf("%I64d\n",ans);
}