首页 > 代码库 > Happy Matt Friends(DP)
Happy Matt Friends(DP)
Happy Matt Friends
Time Limit: 6000/6000 MS (Java/Others) Memory Limit: 510000/510000 K (Java/Others)
Total Submission(s): 3700 Accepted Submission(s): 1407
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 ≤ 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
Sample Output
Source
2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）
//题意:第一行T,然后是2个整数 n,m ,然后给出n个数字，问这些数字任意组合，求异或和大于等于m的组合个数
t题解:暴力DP即可 dp[i][j] 为前 i 个数可以组成异或和等于 j 的个数
dp[i][j] = dp [i-1][j] + dp[i-1][j^num[i]]
可以滚动，可以不滚动
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 #define LL long long 6 #define MX 1000005 7 8 int Scan() { //输入外挂 9 int res = 0, flag = 0;10 char ch;11 if((ch = getchar()) == ‘-‘) flag = 1;12 else if(ch >= ‘0‘ && ch <= ‘9‘) res = ch - ‘0‘;13 while((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)14 res = res * 10 + (ch - ‘0‘);15 return flag ? -res : res;16 }17 18 void Out(int a) { //输出外挂19 if(a < 0) { putchar(‘-‘); a = -a; }20 if(a >= 10) Out(a / 10);21 putchar(a % 10 + ‘0‘);22 }23 24 int n,m;25 int dp[2][1<<21]; // i 个数异或和为 j 个数26 int num[MX];27 28 int main()29 {30 int T;31 cin>>T;32 for(int cnt=1;cnt<=T;cnt++)33 {34 n=Scan(),m=Scan();35 for (int i=1;i<=n;i++)36 scanf("%d",&num[i]);37 memset(dp,0,sizeof(dp));38 dp[0][0]=1;39 for (int i=1;i<=n;i++)40 {41 for (int j=0;j<MX;j++)42 {43 dp[i&1][j]=dp[(i-1)&1][j]+dp[(i-1)&1][j^num[i]];44 }45 }46 LL ans =0;47 for (int i=m;i<MX;i++)48 ans += dp[n&1][i];49 printf("Case #%d: %I64d\n",cnt,ans);50 }51 return 0;52 }
Happy Matt Friends(DP)