Happy Matt Friends（HDU5119 + dp）

【Happy Matt Friends（HDU5119 + dp）】愿君学长松，慎勿作桃李。这篇文章主要讲述Happy Matt Friends（HDU5119 + dp）相关的知识，希望能为你提供帮助。
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5119
题目：

文章图片

题意：
求选择任意个数，使其异或和大于等于m的方案数。
思路：
每个数有选和不选两种方案，显然是背包思想。dp[i][j]表示前i个物品异或和为j时的方案数，转移方程为dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i]]。这题可以考虑用滚动数组滚动掉一维，当然了，不滚动也是可以过滴～
代码实现如下：

1 #include < set> 2 #include < map> 3 #include < deque> 4 #include < ctime> 5 #include < stack> 6 #include < cmath> 7 #include < queue> 8 #include < string> 9 #include < cstdio> 10 #include < vector> 11 #include < iomanip> 12 #include < cstring> 13 #include < iostream> 14 #include < algorithm> 15 using namespace std; 16 17 typedef long long LL; 18 typedef pair< LL, LL> pll; 19 typedef pair< LL, int> pli; 20 typedef pair< int, int> pii; 21 typedef unsigned long long uLL; 22 23 #define lson rt< < 1 24 #define rson rt< < 1|1 25 #define name2str(name)(#name) 26 #define bug printf("**********\\n"); 27 #define IO ios::sync_with_stdio(false); 28 #define debug(x) cout< < #x< < "=["< < x< < "]"< < endl; 29 #define FIN freopen("/home/dillonh/CLionProjects/in.txt","r",stdin); 30 31 const double eps = 1e-8; 32 const int maxn = (1< < 20) + 7; 33 const int inf = 0x3f3f3f3f; 34 const double pi = acos(-1.0); 35 const LL INF = 0x3f3f3f3f3f3f3f3fLL; 36 37 int t, n, m; 38 int a[45], dp[2][maxn]; 39 40 int main() { 41 #ifndef ONLINE_JUDGE 42FIN; 43 #endif 44int icase = 0; 45scanf("%d", & t); 46while(t--) { 47scanf("%d%d", & n, & m); 48int mx = 0, cnt = 0; 49for(int i = 1; i < = n; i++) scanf("%d", & a[i]), mx = max(mx, a[i]); 50memset(dp, 0, sizeof(dp)); 51dp[0][0] = 1; 52while(mx) cnt++,mx > > = 1; 53for(int i = 1; i < = n; i++) { 54for(int j = 0; j < = (1< < cnt); j++) { 55dp[i& 1][j] = dp[(i-1)& 1][j] + dp[(i-1)& 1][j^a[i]]; 56} 57} 58LL ans = 0; 59for(int i = m; i < maxn; i++) ans += dp[n& 1][i]; 60printf("Case #%d: %lld\\n", ++icase, ans); 61} 62return 0; 63 }