link

感觉是一道好题，综合了博弈和计数的技巧，值得一做。

首先不难发现这是一个阶梯博弈的模型，把一枚金币向左移动，相当于把这枚金币和它左边的金币的距离减小，同时它和右边的金币增加等量的距离（这就是阶梯博弈把一个台阶上的一部分石子拿到低一级台阶的过程）。特殊地，最右边一枚金币向左移动相当于把它左侧的一段距离放到右边，拿走的这一些距离也再也无法转移（阶梯博弈中把最低一级台阶的部分石子拿到 $0$ 位置的过程）。

问题转化成把 $n-m$ 个石子放到 $m+1$ 个台阶（$0$ 开始编号）上，求有多少种初始局面使得奇数台阶的石子异或和非 $0$。

这个 $n-m$ 是因为 $n$ 个位置放入 $m$ 枚金币后还剩下 $n-m$ 个位置是我们可以分配的“石子”。$m+1$ 是因为 $m$ 枚金币把棋盘切割成了 $m+1$ 段，每一段都是一个台阶。

求解异或非 $0$ 的方案不好做，我们考虑容斥，求出异或为 $0$ 的方案数，再拿总数去减即可，总方案数为 $C_{n}^m$。容斥的好处是什么？异或和为 $0$，则对于每个二进制位，异或和都是 $0$，也就是有偶数个台阶在这一二进制位上是 $1$。

设计一个计数 dp，$f_{i,j}$ 表示考虑完前 $i$ 个二进制位，用掉了 $j$ 颗石子，合法的方案数量。我们枚举 $i$，$j$，$k$。$k$ 代表这些台阶中有 $k$ 个台阶的第 $i$ 个二进制位为 $1$，得到转移：

$$f_{i,j}=\sum_{k\bmod 2=0}^{k\leq a,k\times 2^i\leq j} f_{i-1,(j-k\times 2^i)\times C_a^k}$$

注：这个式子中二进制位是从 $0$ 开始编号，但是实现的时候防止越界就从 $1$ 开始编。

其中 $a$ 代表奇数编号阶梯的个数，这个直接根据 $n$ 和 $m$ 算出来。

接下来统计所有异或和为 $0$ 的方案，枚举做完所有二进制位用掉的石子个数，剩下的随便丢到偶数编号台阶上，插板就好了（注意这个插板是可以选出空集合的）。

然后容斥一下就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010,mod=1000000009;
int f[20][N],n,m;
int a,b;
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)
			res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}
int jc[N],inv[N];
int C(int n,int m){
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
	cin>>n>>m;
	if(n<m){
		cout<<0;
		return 0;
	}
	jc[0]=inv[0]=1;
	for(int i=1;i<=n;i++){
		jc[i]=(jc[i-1]*i)%mod;
		inv[i]=ksm(jc[i],mod-2);
	}
	n-=m;
	a=(m+1)/2;
	b=m+1-a;
	f[0][0]=1;//未处理任何二进制位，也没有用掉任何石子，方案数为 1
	int bit=log(n)/log(2)+2;
	for(int i=1;i<=bit;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=a&&k*(1<<(i-1))<=j;k+=2)
				f[i][j]=(f[i][j]+f[i-1][j-k*(1<<(i-1))]*C(a,k))%mod;
	int ans=0;
	for(int i=0;i<=n;i++)
		ans=(ans+f[bit][i]*C(n-i+b-1,b-1))%mod;//插板
	cout<<(C(n+m,m)-ans+mod)%mod;
	return 0;
}

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 9;
constexpr int maxn = 1.5e5 + 10;
inline ll qpow(ll a, ll b) {
   ll v = 1;
   for (; b; a = a * a % mod, b >>= 1) {
      if (b & 1) v = v * a % mod;
   }
   return v;
}
ll fac[maxn], ifac[maxn];
ll f[maxn], g[maxn];
inline ll binom(int n, int m) {
   return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
int main() {
   int n, m;
   scanf("%d%d", &n, &m);
   for (int i = fac[0] = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
   ifac[n] = qpow(fac[n], mod - 2);
   for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % mod;
   n -= m;
   int c1 = (m + 1) / 2, c0 = m / 2;
   f[0] = 1ll;
   for (int s = 1; s <= n; s *= 2) {
      memcpy(g, f, sizeof(g));
      memset(f, 0, sizeof(f));
      for (int i = 0; i <= n; i++) {
         for (int j = 0; i + j * s <= n && j <= c1; j += 2) {
            (f[i + j * s] += g[i] * binom(c1, j)) %= mod;
         }
      }
   }
   ll ans = binom(n + m, m);
   for (int i = 0; i <= n; i += 2) {
      ll res = f[i] * binom(n - i + c0, c0) % mod;
      ans = (ans - res + mod) % mod;
   }
   printf("%lld\n", ans);
   return 0;
}