P5363 [SDOI2019] 移动金币
将每颗棋子看成一堆石子，数目为它到左边第一个棋子的空格数。
将棋子向左移动 \(x\) 格会给右边的棋子空出位置，等价于将 \(x\) 颗石子移到右边的石堆。特别地，移动最右边的棋子等价于丢弃石子。
题目中的游戏即为按以上规则操作的的移石子游戏，这实际上为阶梯博弈。从右往左从 \(1\) 开始给石堆编号，则先手必胜等价于奇数号石堆的异或和 \(\ne 0\)。
异或和不为 \(0\) 不好做，换成统计后手必胜的状态，用总方案数减去得到答案。
所有后手必胜的状态相当于 \(n\) 个石子分配到 \(m+1\) 堆石子（分到第 \(m+1\) 堆等价于丢弃），要求其中 \(\lceil\dfrac{m}{2}\rceil\) 堆石子数量的异或和为 \(0\)。
由于异或运算是二进制下按位独立的，设 \(f_{i,j}\) 表示考虑完二进制下前 \(i\) 位，还剩 \(j\) 颗石子的方案数。
转移时该位下为 \(1\) 的数量，为保证异或和为 \(0\) 只枚举偶数。
具体地：
\[f_{i,j}=\sum_{k\equiv 0\pmod 2} \binom{\lceil\dfrac{m}{2}\rceil}{k}f_{i-1,j+k\times 2^{i-1}}
\]
#include<bits/stdc++.h>
#define N 150005
using namespace std;
int n,m;constexpr int P=1000000009;
long long ans,f[2][N],fac[N],ifac[N];
int inv(int x,int y=P-2){int res=1;for(;y;x=1ll*x*x%P,y>>=1)if(y&1) res=1ll*res*x%P;return res;
}
int C(int x,int y){return fac[x]*ifac[y]%P*ifac[x-y]%P;}
int main(){scanf("%d%d",&n,&m);fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;ifac[n]=inv(fac[n]);for(int i=n;i;i--) ifac[i-1]=ifac[i]*i%P;int K=m+1>>1;ans=C(n,m),f[0][n-=m]=1,m-=K;for(int i=1,t=n,v;i<20;i++,t=v){v=max(t-(K-(K&1))*(1<<i-1),0);memset(f[i&1]+v,0,sizeof f[i&1]-(v<<3));for(int j=t;j<=n;j++)for(int k=0,s=0;k<=K&&s<=j;k+=2,s+=1<<i)(f[i&1][j-s]+=f[i&1^1][j]*C(K,k))%=P;}for(int i=0;i<=n;i++) (ans-=f[1][i]*C(i+m,m))%=P;printf("%lld",(ans+P)%P);return 0;
}