HDU 5119 Happy Matt Friends（dp）

Happy Matt Friends

Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 510000/510000 K (Java/Others)

Total Submission(s): 3047    Accepted Submission(s): 1203

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 ≤ 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.  

Sample Input

2
3 2
1 2 3
3 3
1 2 3
        

Sample Output

Case #1: 4
Case #2: 2


   
    
     Hint
    In the first 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個數中找出滿足異或和不小于M的方案總數。

dp[i][j]：第i個位置異或值為j的方案數；

第i-1個位置的異或值為j的方案數為第i個位置異或值為j的方案數一部分，同時也是第i個位置異或值為j^k[i]方案數的一部分；

然後令i:1~n j:0~INF 算出每個位置每個異或值的情況數；

開始時要初始化dp[1][k[1]] dp[1][0]，因為後面會用到；

最後令i:m~INF 将所有滿足條件的dp[n][i]累加；

TIPs：long long~

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=50;
const int INF=(1<<20)+10;
int k[N];
ll dp[N][INF];
int main(){
	int t,cas=1;
	scanf("%d",&t);
	while(t--){
		int n,m;
		ll ans=0;
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&k[i]);
		}
		memset(dp,0,sizeof(dp));
		dp[1][0]=dp[1][k[1]]=1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<INF;j++){
				dp[i][j]+=dp[i-1][j];
				dp[i][j^k[i]]+=dp[i-1][j];
			}
		}
		for(int i=m;i<=INF;i++){
			ans+=dp[n][i];
		}

		printf("Case #%d: %lld\n",cas++,ans);
	}
}
           

面向題解做題系列= =一開始就搜了一下發現是DP然後才知道大概要怎麼做唉……獨立思考我應該是想不到要醬紫做的~