思路:
(1)条件及问题:给定N个数,找到异或值大于等于M的总方案数;
(2)分析:
- 可以dfs()枚举,超时;
- 考虑dp,dp[i][j]描述在前i个数中选,值为j的方案数;
- 则dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^a[i]];
代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define maxx 1024*1024
int a[45];
ll dp[45][maxx];///dp[i][j]代表从第1个数到第i个数,亦或后结果为j的方案的数目
///任何数和0异或后的·结果依然是本身
int main()
{
int t,n,m,c=1;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
dp[0][0]=1;
for(int i=1; i<=n; i++)
for(int j=0; j<maxx; j++)
dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]];
ll sum=0;
for(int k=m; k<maxx; k++)
sum+=dp[n][k];
printf("Case #%d: %lld\n",c++,sum);
}
}