
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5119
分析:dp[i][j]表示由前i个数组成异或和为j的方法数,则dp[i][j]=d[i-1][j^a[i]]+dp[i][j];
边界:dp[0][0]=1,其他为0;复杂度40*1e6
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define inf 1<<30
#define mod 1000000007
using namespace std;
int a[];
int dp[][(<<)];
int main()
{
int T,n,m;
int cas=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
for(int i=; i<=n; i++)scanf("%d",&a[i]);
int pre=,cur=;
dp[][]=;
for(int i=; i<=n; i++)
{
memcpy(dp[cur],dp[pre],sizeof(dp[pre]));//小于i个数异或和为j的方法要赋值给现在
for(int j=; j<=(<<)-; j++)
{
int num=j^a[i];
if(dp[pre][num])
{
dp[cur][j]+=dp[pre][num];
}
}
swap(pre,cur);
}
LL ans=;
for(int i=m; i<=(<<)-; i++)ans+=dp[pre][i];
printf("Case #%d: ",cas++);
printf("%I64d\n",ans);
}
}