这一题求得是方案总数,所以和平时写的 f[i][sum]=max(f[i-1][sum],f[i-1][k[i]^sum]+1);的背包不太一样……吧?
这里面的状态转移方程是f[i][sum]=f[i-1][sum]+f[i-1][pre_sum]; f[i][sum]表示取了前i个数,异或和是sum。
因为10^6二进制是20bit,所以异或和最大是1<<20
f[i][sum]的状态由之前的两个状态转移过来,一个是i-1没取k[i],一个是i-1取了k[i],pre_sum^k[i]=sum,So that pre_sum=k[i]^sum
注意这里的方案数最多会有2^40个,所以f[i][sum]要用long long,另外sum=0也是一种方案(不取任何一个数),对应的f[i][sum]=1;
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<ctype.h> #include<map> #include<time.h> #include<bitset> using namespace std; //hdu 5119 //1<<20=1048575 const int maxn=50; int T; int N; int M; int k[maxn]; long long f[maxn][(1<<20)+10]; int main() { freopen("input.txt","r",stdin); //freopen("data.txt","r",stdin); //freopen("out1.txt","w",stdout); scanf("%d",&T); for(int ca=1;ca<=T;ca++) { scanf("%d %d",&N,&M); for(int i=1;i<=N;i++) { scanf("%d",&k[i]); } memset(f,0,sizeof(f)); //f[0][0]=1; //选0个也是一种方案 f[1][0]=1; f[1][k[1]]=1; for(int i=2;i<=N;i++) { for(int sum=0;sum<1048576;sum++) { f[i][sum]=f[i-1][sum]+f[i-1][k[i]^sum]; // if(f[i-1][k[i]^sum]!=0)//排除不存在的情况 // { // f[i][sum]=max(f[i-1][sum],f[i-1][k[i]^sum]+1); // // } // else // { // f[i][sum]=f[i-1][sum]; // } } } // for(int i=0;i<100;i++) cout<<f[1][i]<<" "; long long ans=0; for(int i=M;i<1048576;i++) { ans+=f[N][i]; } printf("Case #%d: %I64d\n",ca,ans); } return 0; }