P5970 [POI2016]Nim z utrudnieniem

· · 题解

P5970 [POI2016]Nim z utrudnieniem 题解

题目传送门

思路

Nim 游戏各堆异或和是否为零即可判断答案，不必多说，关键在于扔掉石子的操作。设原来石子的异或和为 s，如果扔掉的异或和为 s，那么就能使得异或和为 0，后手就能获胜。考虑用动态规划解决问题。设 f_{i,j,k} 表示前 i 堆中，在 \mod d 的情况下去了 j 堆，取的堆异或和为 k 的方案数。易得 f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k\oplus a_i}，前者表示什么都不做，后者表示新取了一堆共 a_i 个石子。如果直接这样做时间复杂度是 O(nda_{\max})，无法承受，这里又要用到一个小技巧了：一个数与比它小的数异或不会超出其二倍。这样复杂度就能降到 O(dm)。然后需要注意一点，这里如果想要用一个数组记录，无法像背包一样直接做，因为这里的依赖是循环依赖，如果 j=0，需要从 d-1 转移，这是需要先处理 j=0 的，临时存储，然后最后再覆盖。

代码


#include<bits/stdc++.h>
using namespace std;
#define L(i,l,r) for(int i=l;i<=r;++i)
#define R(i,l,r) for(int i=r;i>=l;--i)
const int N=500010,D=11,mod=1e9+7;
int n,d,f[D][4*N],a[N],g[4*N],s;
int main(){
    scanf("%d%d",&n,&d);
    L(i, 1, n)scanf("%d",a+i),s^=a[i];
    sort(a+1,a+1+n);
    f[0][0]=1;
    int u=1;
    L(i, 1, n){
        while(u<=a[i])u<<=1;
        L(j, 0, u-1)g[j]=(f[d-1][j^a[i]]+f[0][j])%mod;
        R(j, 1, d-1)
            L(k, 0, u-1)f[j][k]=(f[j][k]+f[j-1][k^a[i]])%mod;
        L(j,0,u-1)f[0][j]=g[j];
    }
    if(n%d==0)f[0][s]--;
    if(f[0][s]<0)f[0][s]+=mod;
    printf("%d",f[0][s]);
    return 0;
}