HDU5119 Happy Matt Friends（DP+滚动数组）
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 ≤ 106).
In the second line, there are N integers ki (0 ≤ ki ≤ 106), 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个数中任意k个数异或和大于等于m的方案数。
建立状态dp[i][j]表示i个数中异或和为j的个数。状态转移方程是dp[i][j]+=dp[i-1][j](不选择第i个数）dp[i][j^a[i]]+=dp[i-1][j] (选择第i个数）。用滚动数组优化去掉第一个下标。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<functional>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+10,NN=1<<20,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
int n,m,num;
ll k[41],dp[NN][2];
void init(){num=0;memset(dp,0,sizeof dp);
}
int main(){int t,T=0;scanf("%d",&t);while(t--){init();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&k[i]);dp[0][0]=1;printf("Case #%d: ",++T);for(int i=1;i<=n;i++){for(int j=0;j<NN;j++) dp[j][num^1]=dp[j][num]+dp[j^k[i]][num];num^=1;}ll ans=0;for(int i=m;i<NN;i++) ans+=dp[i][num];//从m开始遍历到1<<20即可找到>=m的数有几个printf("%lld\n",ans);}
}