题目链接:传送门
题意:
给定n个数,求从中选出任意个数异或起来值大于m的方案数。
分析:
动态规划,设dp[i][j] 表示第几次选第i个数的时候异或起来
值为j的方案数。dp[i][j^a[i]]+=dp[i][j];但是对空间有要求
我们可以用滚动数组来写。
代码如下:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1<<20;
typedef long long LL;
LL dp[2][maxn];
int a[50];
int main()
{
int t,n,m,cas=1;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
LL ans=0;
int cnt = 0;
dp[0][0]=1;
for(int i = 0; i < n; ++i) {
memset(dp[cnt^1],0,sizeof(dp[cnt^1]));
for(int j = 0; j < maxn; ++j) {
int tmp = j^a[i];
dp[cnt^1][tmp] += dp[cnt][j];
dp[cnt^1][j] += dp[cnt][j];
}
cnt ^= 1;
}
for(int i =m;i<maxn;i++)
ans+=dp[cnt][i];
printf("Case #%d: %I64d\n",cas++,ans);
}
return 0;
}