本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-27 18:21:37

本题披着博弈论的外衣，实际上，除了第一步用 Nim 定理转化题意以外，跟博弈论没什么关系。

题意

给定一个长度为 $n$ 的非负整数数组。

给定 $q$ 次询问，每次给定一个区间 $[l,r]$，问这个区间最多删除多少个位置，使得剩下的位置上的数异或和为 $0$。

不能删完，同时求出能使删除数字数量最多的方案数量。

两个方案不同当且仅当删除的位置的集合不同。

无解输出 $-1$。

做法

注意到值域是 $[0,50]$，也就是说最多有 $51$ 种数字。

对于每一种数字，其最多保留 $2$ 个，证明是假如最优解中出现多于 $2$ 个相同的数字，那么可以删除两个这样的数字得到更优的解。

随后 dp，$dp_{i,j,0/1}$ 代表前 $i$ 种数字，保留的数字异或和为 $j$，且前 $i$ 个数字是否全部删除。

状态转移的话，只需要对于每种数字，枚举其保留了几个，转移是显然的。

这是我的 dp 转移的代码：

int rem[51];\/\/ 每种数字出现的次数
int top;\/\/ 有多少不同的数字
dp[0][0][0]=0;\/\/ 最多删多少个
ways[0][0][0]=1; \/\/ 保证删最多个的方案数
auto ckmxdp=[&](int nxti,int nxtj,int nxtk,int i,int j,int k,int add,ll waymult)->void{
    \/\/ nxti,nxtj,nxtk 代表新的状态，i,j,k 是旧的状态，add 是旧的状态转移后 dp 值加上多少,waymult 是本次选保留的位置的方案数。
    if(dp[nxti][nxtj][nxtk]<dp[i][j][k]+add){
        dp[nxti][nxtj][nxtk]=dp[i][j][k]+add;
        ways[nxti][nxtj][nxtk]=ways[i][j][k]*waymult;
    }else if(dp[nxti][nxtj][nxtk]==dp[i][j][k]+add){
        ways[nxti][nxtj][nxtk]+=ways[i][j][k]*waymult;
    }
    ways[nxti][nxtj][nxtk]%=mod;
};
for(int i=0;i<top;i++){
    for(int j=0;j<=63;j++){
        for(int k=0;k<=1;k++){
            \/\/ 当前这个数不对总 xor 造成影响。  
            \/\/ 情况：保留 0 或 2 个。
            ckmxdp(i+1,j,k,i,j,k,rem[i+1],1);
            if(rem[i+1]>=2){
                ckmxdp(i+1,j,1,i,j,k,rem[i+1]-2,((ll)rem[i+1]*(rem[i+1]-1)\/2)%mod);
            }
            \/\/ 当前这个数对总 xor 造成影响。  
            \/\/ 情况：保留 1 个.
            if(rem[i+1]>=1){
                ckmxdp(i+1,j^b[i+1],1,i,j,k,rem[i+1]-1,rem[i+1]);
            }
        }
    }
}
if(dp[top][0][1]>=0){
    printf("%d %lld\n",dp[top][0][1],(ways[top][0][1]%mod+mod)%mod);
}else{
    puts("-1");
}