hdu 5119 - Happy Matt Friends（dp解法）

Feb 17, 2015 · 2 min read · 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 ≤ 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    }
47    
48