题面
一枚金币向左移若干格等价若干个空格向右移一个金币，终状态为所有空格在最右，转换为阶梯博弈
阶梯博弈
每个阶梯上有若干枚石子，每次操作将同个阶梯的任意石子向下移一个阶梯，不能操作者输
等价对奇数阶梯做Nim博弈
先手按Nim博弈操作。若对方移动偶数阶梯，则将对方移动石子继续下移到偶数阶梯；否则按Nim博弈操作。
此时先手移动后奇数阶梯上无石子，对方移动偶数（>0）阶梯，先手继续下移到偶数（>=0）阶梯，直至对方无法操作。当奇数阶梯异或和不为0，先手必胜。
思路
题目等价将n-m个石子放入m+1个盒子，使得偶数（下标以1开始）盒子异或和为0的方案的补集。
异或和为0转换为二进制每一位1的个数为偶数，做计数dp
设\(dp_{i,j}\)为放入前i位1，剩下j个石子未放入的方案数
\[dp_{i,j} = \sum_{k\%2=0}^{\frac{m+1}{2}} dp_{i-1,j+2^{i-1}\times k}\times \begin{pmatrix} \frac{m+1}{2} \\k \\\end{pmatrix} \]再将剩下的石子用插板法放入奇数盒
最后用总方案减去即为答案
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1.5e5+10,mod=1e9+9;
#define int long long
int n,m,dp[20][MAX],ans,f[MAX],inv[MAX];
inline int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
return x;
}
inline int C(int n,int m){
return f[n]*inv[m]%mod*inv[n-m]%mod;
}inline int power(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;b>>=1;
}return res;
}
signed main(){
n=read();m=read();
f[0]=1;
for(int i=1;i<=n;++i) f[i]=f[i-1]*i%mod;
inv[n]=power(f[n],mod-2);
for(int i=n-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
dp[0][n-m]=1;int q=__lg(n-m)+1;
for(int i=1,p=1;i<=q;++i,p<<=1)
for(int j=0;j<=n-m;++j)
for(int k=0;(k<=m+1>>1)&&(j+p*k<=n-m);k+=2)
dp[i][j]=(dp[i-1][j+p*k]*C(m+1>>1,k)%mod+dp[i][j])%mod;
for(int i=0;i<=n-m;++i)
ans=(ans+dp[q][i]*C(i+(m>>1),m>>1)%mod)%mod;
ans=(C(n,m)-ans+mod)%mod;
printf("%lld",ans);
}