hdu 5119 Happy Matt Friends (dp)

Problem Description

Matt has N friends. They are playing a game together.

Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.

 

Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10⁶).

In the second line, there are N integers ki (0 ≤ k_i ≤ 10⁶), indicating the i-th friend’s magic number.

 

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

 

Sample Input

2

3 2

1 2 3

3 3

1 2 3

 

Sample Output

Case #1: 4

Case #2: 2

   题意：给出n个数，求n个数中几个数通过异或运算得到m的个数。

   思路：设dp[i][j]为前i个数中异或为j的个数，dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]];这dp[i-1][j]很容易懂，就不解释了，对于dp[i-1][j^a[i]]，因为j^a[i]^a[i]=j;所以j^a[i]就是前i-1个数中异或能的到j的个数。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long dp[3][2000006];
int main()
{
    long long t,n,m,i,j,k=1;
    long long ans;
    int a[44];
    scanf("%I64d",&t);
    while (t--)
    {
        scanf("%I64d%I64d",&n,&m);
        for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for (i=1;i<=n;i++)
        {
            for (j=0;j<=2000004;j++)
            dp[i%2][j]=dp[(i-1)%2][j]+dp[(i-1)%2][j^a[i]];
        }
        ans=0;
        n=n%2;
        for (i=m;i<=1400000;i++) ans+=dp[n][i];
        printf("Case #%I64d: %I64d
",k,ans);
        k++;
    }
}