HDU-5119 Happy Matt Friends （背包DP，递推枚举）

追风赶月莫停留，平芜尽处是春山。这篇文章主要讲述HDU-5119 Happy Matt Friends （背包DP，递推枚举）相关的知识，希望能为你提供帮助。
题意：n个物品，第i个物品的权值为ki，选出一些物品使它们的异或不小于m，求有多少种方案
数据范围：1 < = n < = 40，0 < = m < = 1e6
思路：其实就是换了一种要求的背包，MX要开得比1e6大一些，不滚动数组也能过去。
老套路设dp[i][j]为前i个物品异或为j时的方案，dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i]]，最后把dp[n][m以上]的值求和

1 #include< cstdio> 2 #include< cstring> 3 #include< algorithm> 4 #define LL long long 5 using namespace std; 6 7 const int mx = 1< < 20; 8 int a[50]; 9 LL dp[50][mx+10]; 10 11 int main(){ 12int t, kase = 0; 13scanf("%d", & t); 14while (t--){ 15int n, m; 16memset(dp, 0, sizeof dp); 17LL ans = 0; 18scanf("%d%d", & n, & m); 19for (int i = 1; i < = n; i++) 20scanf("%lld", & a[i]); 21dp[0][0] = 1; 22for (int i = 1; i < = n; i++) 23for (int j = 0; j < = mx; j++) 24dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i]]; 25for (int i = m; i < mx; i++) 26ans += dp[n][i]; 27printf("Case #%d: %lld\n", ++kase, ans); 28} 29return 0; 30 }

【HDU-5119 Happy Matt Friends （背包DP，递推枚举）】