基础DP, 滚动数组
题目大意：给你N个数，问有多少个子集，满足子集内所有数的xor和大于等于M
本题要点：
1、状态表示：
dp[i][j] 表示前i个数，xor和为j的情况有多少种.
这里用滚动数组（来两行数组）来存， long long dp[2][MaxN]。
2、状态转移：
dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]]
dp[i - 1][j] 表示不选 a[i] 这个数
dp[i - 1][j ^ a[i]] 表示选择a[i] 这个数（注意到 j ^ a[i] ^ a[i] == j）
写成滚动数组，也就是 dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[(i - 1) % 2][j ^ a[i]]
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = (1 << 20) + 10;
int T, n, m;
int a[45];
long long dp[2][MaxN]; //dp[i % 2][j] 表示前i个数，xor和为j的情况有多少种void sovle(int t)
{
memset(dp, 0, sizeof dp);dp[0][0] = 1;for(int i = 1; i <= n; ++i){
for(int j = 0; j < 1 << 20; ++j){
dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[(i - 1) % 2][j ^ a[i]]; }}long long ans = 0;for(int i = m; i < 1 << 20; ++i){
ans += dp[n % 2][i];}printf("Case #%d: %lld\n", t, ans);
}int main()
{
scanf("%d", &T);for(int t = 1; t <= T; ++t){
scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);}sovle(t);}return 0;
}/* 2 3 2 1 2 3 3 3 1 2 3 *//* Case #1: 4 Case #2: 2 */