题目的意思是从n个数里面选取任意个数进行异或,请问他们组合异或的值大于m的情况有多少种?

定义dp[i][j]为前i个人异或得到j的情况,则dp方程为:

dp[i%2][j]+=dp[(i-1)%2][j];            //当前这个人不进行异或

dp[i%2][j^res[i]]+=dp[(i-1)%2][j]; //当前这个人进行异或

最后从m循环一下到异或能到的最大值累加即可。有可能会爆内存,看题解后第一次写虽然AC了,但是发现内存占用高达177MB,然后用滚动数组优化之后就是17MB了。(昨天用滚动数组一直WA或者RE,今天突然想到,特么每次计算完之后忘记给上一行清零了。。。)


代码:

StatusAccepted
Time1092ms
Memory17216kB
Length800
LangG++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=45;
const int maxm=1000005;
int res[maxn], dp[2][maxm*2];
int t, n, m, cas=1;
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i=1;i<=n;i++)
            scanf("%d", &res[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<maxm;j++){
                dp[i%2][j]+=dp[(i-1)%2][j];
                dp[i%2][j^res[i]]+=dp[(i-1)%2][j];
            }
            for(int j=0;j<maxm;j++){
                dp[!(i%2)][j]=0;
            }
        }
        long long ans=0;
        for(int i=m;i<maxm;i++)
            ans+=dp[n%2][i];
        printf("Case #%d: %lld\n", cas++, ans);
    }
    return 0;
}