题意：给定n个数，从中分别取出0个，1个,2个...n个，并把他们异或起来，求大于m个总的取法。
思路：dp，背包思想，考虑第i个数，取或者不取，dp[i][j]表示在第i个数时，异或值为j的所有取法。dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]]);
其中dp[i - 1][j]表示不取第i个数，dp[i - 1][j ^ a[i]]表示取第i个数，由于40比较大，所以用滚动数组优化，后一个状态需要前一个来推导，而和前一个之前的所有的没有关系，所以之保存上一个就行了。
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; typedef long long ll; const int maxn = (1 << 20); int a[43]; int dp[2][maxn];//滚动数组,一共就需要两个状态,求第i个状态只需要i-1个状态 int main() { int T, n, m, kase = 0; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < maxn; j++) dp[i & 1][j] = dp[(i - 1) & 1][j] + dp[(i - 1) & 1][j ^ a[i]]; } ll ans = 0; for (int i = m; i < maxn; i++) ans += dp[n & 1][i];//最后的答案保存在n&1这一维中 cout << "Case #" << ++kase << ": " << ans << endl; } return 0; }