首先可以把问题转化一下：m堆石子，一共石子数不超过(n-m)颗，每次可以将一堆中一些石子推向前一堆，无法操作则失败，问有多少种方法使得先手必胜？
然后这个显然是个阶梯Nim，然后有这样的结论：奇数层异或和为0。具体证明：参考这篇博客，当然不是我写的。如果不知道结论，里面有例题POJ1704可以做一下。
然后直接DP显然会T飞，考虑一个按位DP的技巧，f[i][j]表示确定前i位异或起来为0，剩下j个棋子的方案数。组合数相乘转移，注意一些细节即可。
#include<bits/stdc++.h> using namespace std; const int N=151000,mod=1e9+9; int n,m,ans,f[19][N],fac[N],inv[N]; int C(int a,int b){return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;} int main() { cin>>n>>m; fac[0]=inv[0]=inv[1]=1;for(int i=2;i<=n+m;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=n+m;i++)fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod; ans=C(n,m),n-=m; f[18][n]=1; for(int i=17;~i;i--) for(int j=0;j<=n;j++) for(int k=0;j+(2*k<<i)<=n&&k<=(m+1)/4;k++) f[i][j]=(f[i][j]+1ll*f[i+1][j+(2*k<<i)]*C((m+1)/2,2*k))%mod; for(int i=0;i<=n;i++)ans=(ans-1ll*f[0][i]*C(i+m/2,m/2)%mod+mod)%mod; cout<<ans; }