不错的博弈 + 计数。
不难发现题中的游戏是阶梯 Nim 的变体。若设 \(a_i\) 为第 \(i\) 枚金币的位置，令 \(\forall i \in [2,m],\ b_i = a_i - a_{i-1},\ b_1 = a_1 - 1,\ b_{m+1} = n - a_m\)，则每次可以做的就是选择 \(i \in [1,m],\ x \in [1,b_i]\)，将 \(b_i \gets b_i - x,\ b_{i+1} \gets b_{i+1} + x\)。这就是一个 reversed 的阶梯 Nim，结论是先手必胜当且仅当从右往左所有第偶数位的 \(b_i\) 异或和 \(\ne 0\)。
考虑容斥后转化为异或和 \(=0\)。考虑 dp，\(f_{i,j}\) 表示当前考虑到第 \(i\) 位，数的和是 \(j\)。那么每次枚举当前位有 \(k\) 个数是 \(1\)（需要满足 \(2\,|\,k\) 且 \(j + k2^i \le n\)），\(f_{i+1,j+k2^i} \gets f_{i+1,j+k2^i} + f_{i,j} \times \binom{(m+1)/2}{k}\)。最后枚举和，隔板法统计答案即可。
时间复杂度 \(O(nm \log n)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int maxm = 20;
const int N = 200000;
const ll mod = 1000000009;
ll n, m, fac[maxn], ifac[maxn], f[maxm][maxn];
ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
n -= m;
f[0][0] = 1;
int t = 0;
for (int i = 0; (1 << i) <= n; ++i) {
t = i + 1;
for (int j = 0; j <= n; j += 2) {
for (int k = 0; k <= (m + 1) / 2; k += 2) {
if (j + (k << i) <= n) {
f[i + 1][j + (k << i)] = (f[i + 1][j + (k << i)] + f[i][j] * C((m + 1) / 2, k) % mod) % mod;
}
}
}
}
ll ans = 0;
for (int i = 0; i <= n; ++i) {
ans = (ans + f[t][i] * C(n - i + m / 2, m / 2) % mod) % mod;
}
printf("%lld\n", (C(n + m, m) - ans + mod) % mod);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}