其实还是穷举子集类的dp,一般这种dp我们只需要用一个一维的滚动数组就可以了,但是这个题目状态转移的时候不但可能向后还有可能向前,所以这次得用二维数组.
状态方程 dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]],分别表示第i个数不取和第i个数取情况下状态.

代码如下:

#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 2100000 ///太小就会WA int dp[50][maxn]; int num[50]; int main() { int t,Case=0; scanf("%d",&t); while(t--) { int n,m; memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); int Max=(1<<20); dp[0][0]=1; ///利用j^num[i]^num[i]=j进行状态转移 ///即dp[i-1][j]是由dp[i-1][j^num[i]]再^num[i]得到的 ///dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]] for(int i=1;i<=n;i++) { for(int j=0;j<=Max;j++) dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]]; } long long sum=0; for(int i=m;i<=Max;i++) sum+=dp[n][i]; printf("Case #%d: %lld\n",++Case,sum); } return 0; }