hdu5119 DP

分析题目 发现很多都是重叠的部分。然后dp求解。

用一维来存xor后的值，那么所有的情况都能够表示了。

#include<stdio.h>
#include<string.h>
#define ll long long
const int maxn = 1000000;
ll dp[50][maxn];
int m,n;
int a[50],ff;
void slove()
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<maxn;j++)
            dp[i][j]+=dp[i-1][j];
        for(j=0;j<maxn;j++)
        {
            dp[i][j^a[i]]+=dp[i-1][j];
        }
    }
    ll ans=0;
    for(i=m;i<maxn;i++)
        ans+=dp[n][i];
    printf("Case #%d: %lld
",++ff,ans);
}
int main()
{
    int i,j,t;
    ff=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        dp[1][0]=dp[1][a[1]]=1;
        slove();
    }
}