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 6).
In the second line, there are N integers ki (0 ≤ k i ≤ 10 6), 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.
正解貌似是高斯消元….不会的说….PYY说不就是解方程么….然后我去看了下…..挺多概念没学线代的话还是挺眼生的…（orzpyy大神）记得高三的时候做过一个用矩阵加速求线性递推式的东西….当时10^18的数据秒过….还是挺让我惊讶了一下… 扯远了… 这题dp也能做，有点类似01背包（dp真是够渣，寒假看看能不能抽时间弄一下，依然是最大的短板） 只不过状态转移方程是 dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]] 然后正常些貌似会MLE。。。。。用到了滚动数组 其实滚动数组,完全…没有理解的难度啊 竟然是我第一次使用，大概是因为基本没怎么做过DP的题吧，而滚动数组这个优化貌似主要在Dp的题里需要… 然后在搜滚动数组的时候，看到一篇博客里用异或来表示两个状态我觉得这一点也很赞….. 我自己想的话的大概就要又加，又mod，然后还得再来一个变量了吧…..差评满满 还有位运算….是挺神的东西….目前还处于一知半解的阶段….ORZ M67大神
1
2 /* ***********************************************
3 Author :111qqz
4 Created Time :2016年02月19日 星期五 16时30分04秒
5 File Name :code/hdu/5119.cpp
6 ************************************************ */
7
8 #include<iostream>
9 #include<cmath>
10 #include<cstring>
11 #include<algorithm>
12 const long long C=1<<21;
13 long long dp[2][C];
14 using namespace std;
15
16 int main()
17 {
18 int t,a[49];
19 cin>>t;
20 int tt;
21 tt=t;
22 while (t--)
23
24 {
25 int n,m,roll;
26 roll=0;
27 memset(dp,0,sizeof(dp));
28 dp[0][0]=1;
29 cin>>n>>m;
30 for(int i=0;i<n;i++)
31 cin>>a[i];
32
33 for(int i=0;i<n;i++)
34 {
35 roll=roll^1;
36 for(int j=0;j<=(C/2);j++)
37 dp[roll][j]=dp[roll^1][j]+dp[roll^1][j^a[i]];
38 }
39 long long ans=0;
40 for(int i=m;i<=(C/2);i++)
41 ans=ans+dp[roll][i];
42 cout<<"Case #"<<tt-t<<": "<<ans<<endl;
43
44 }
45 return 0;
46 }