N*M暴力DP....

Happy Matt Friends

2
3 2
1 2 3
3 3
1 2 3

Case #1: 4
Case #2: 2

Hint
In the ?rst sample, Matt can win by selecting:
friend with number 1 and friend with number 2. The xor sum is 3.
friend with number 1 and friend with number 3. The xor sum is 2.
friend with number 2. The xor sum is 2.
friend with number 3. The xor sum is 3. Hence, the answer is 4.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

LL dp[2][1<<20+1];
int a[100];
int n,m;

int main()
{
    int T_T,cas=1;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        int now=1,pre=0;
        dp[0][0]=1LL;
        for(int i=1;i<=n;i++)
        {
            memset(dp[now],0,sizeof(dp[now]));
            for(int j=0;j<=(1<<20);j++)
            {
                if(dp[pre][j])
                {
                    int x=j^a[i];
                    dp[now][x]+=dp[pre][j];
                    dp[now][j]+=dp[pre][j];
                }
            }
            swap(now,pre);
        }
        LL ans=0;
        for(int i=m;i<=(1<<20);i++)
            ans+=dp[pre][i];
        printf("Case #%d: %I64d\n",cas++,ans);
    }
    return 0;
}

HDOJ 5119 Happy Matt Friends DP

原文：http://blog.csdn.net/ck_boss/article/details/41606923