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.
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.
For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10 6).
In the second line, there are N integers ki (0 ≤ k i ≤ 10 6), indicating the i-th friend’s magic number.
2 3 2 1 2 3 3 3 1 2 3
Case #1: 4
Case #2: 2
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.
【题意】 题意说有N个朋友，每个人都有一个魔法数字，现在要从这N个人中选出一些人，使得他们所拥有的的数字的亦或值大于M，求所有的方案数。
一开始还以为是个数学题，但是却出现在动态规划的专题了，想了好久还是不会，看了大牛们的博客，才知道这题是暴力解。
因为这题给的数据范围是40个数，每个数小于10^6，所以这些数的最大亦或值也就2^20，所以直接暴力解，然后在大于给的M的范围内求和即为所求。
不得不说这方法很厉害，能想出这方法的人也一定是大牛中的大牛，佩服。
【AC代码】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50;
int m,n;
int a[N];
__int64 dp[2][(1<<20)+5];//这儿里面一定要加括号，不然会爆内存int main()
{int t,cnt=0;scanf("%d",&t);while(t--){while(~scanf("%d%d",&m,&n)){for(int i=1;i<=m;++i)scanf("%d",&a[i]);sort(a,a+m);memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=m;i++){for(int j=0;j<(1<<20);j++)//每个数都有两种状态，取或者不取dp[i%2][j]=dp[(i-1)%2][j]+dp[(i-1)%2][j^a[i]];}__int64 ans=0;//注意类型 会爆intfor(int i=n;i<(1<<20);++i){ans+=dp[m%2][i];}printf("Case #%d: %I64d\n",++cnt,ans);}}return 0;
}