题解：CF2043F Nim

__vector__ · 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");
}