[洛谷P5363][题解][SDOI2019]移动金币

事实上如果不事先了解，还是挺难独立看出这题的结论的。

容易发现本题的操作就是将左边的一段空格切出来给右边。我们抽象一下就是若干堆石子，每次可以从某一堆拿出若干颗到其右侧邻堆。这种阶梯 nim 有一个好看的结论：直接对从右数的偶数堆玩普通 nim 即可。因为对奇数堆操作后对手一定可以马上将其移到下一个奇数堆，这样对奇数堆的操作就都没用；而对偶数堆的操作就是将若干颗石子变成没用的奇数堆石子，这样就等价于普通 nim。

所以原题就是求将 \(n-m\) 个石子分成 \(m+1\) 组，使得偶数堆的石子个数异或和等于零。

我们可以设 \(f_{i,j}\) 表示放了前 \(i\) 位，当前和为 \(j\) 的方案数，根据偶数堆的每一位都有偶数个 \(1\) 的性质转移。

const int N=150010,M=60,p=1e9+9;
int n,m,C[N][M],f[20][N],cnt[M];
int main(){
  Read(n),Read(m),C[0][0]=1;
  for(int i=1;i<=n;i++){
    C[i][0]=1;
    for(int j=1;j<=min(i,m);j++){
      C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
  }
  int ans=C[n][m];m++,n=n-m+1,f[18][0]=1;
  for(int i=0;i<=m;i++){
    for(int j=0;j<=i;j+=2){
      (cnt[i]+=(LL)C[m/2][j]*C[m-m/2][i-j]%p)%=p;
    }
  }
  for(int i=18;i;i--){
    for(int j=0;j<=n;j++){
      if(!f[i][j])continue;
      for(int k=0;k<=m;k++){
        if(j+k*(1<<i-1)>n)continue;
        (f[i-1][j+k*(1<<i-1)]+=(LL)f[i][j]*cnt[k]%p)%=p;
      }
    }
  }
  printf("%d\n",(ans-f[0][n]+p)%p);
  KafuuChino HotoKokoa
}