HDU 5119 Happy Matt Friends (14北京区域赛 类背包dp)

happy matt friends

time limit: 6000/6000 ms (java/others)    memory limit: 510000/510000 k (java/others)
total submission(s): 5188    accepted submission(s): 1985

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

hint

in the first 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.

 

题意：题目大意：n个数，从中挑k个，使得这k个数的异或和不小于m，问有多少种挑选方法（0<=k<=n)

思路：dp[i][j]表示前 i 个数中选择一些使得异或和为j的方法数，转移方程：dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]]，即等于前i－1个异或和为j的方法数（第i个数不需要进行异或）加上前i－1个异或和为j ^ a[i]的方法数（第i个数需要异或），因为j ^ a[i] ^ a[i] == j ^ (a[i] ^ a[i]) == j ^ 0 ＝ j，最后再累计一下j大于等于m时的方法数，这题内存给的够大，也可以直接采用滚动数组

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define eps 1e-10
#define ll long long
int const maxn = (1<<20);
const int mod = 1e9 + 7;
int gcd(int a, int b) {
    if (b == 0) return a;  return gcd(b, a % b);
}

int a[42];
ll dp[42][maxn];
int main()
{
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--)
    {
        int n,m;
        
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<maxn;j++)
                dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]];   //如果前i-1个数异或值是j就不需要将第i个数进行异或，如果前i-1个数有异或后是j^a[i]的，那么第i个数进行异或，刚好可以得j
        ll ans=0;
        printf("case #%d: ",ca++);
        for(int i=m;i<maxn;i++)
            ans+=dp[n][i];
        printf("%lld\n",ans);
    }
    return 0;
}