题目描述
一个 (1 imes n) 的棋盘上最初摆放有 (m) 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。
Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作，且 Alice 先行。当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。金币不能被移出棋盘，也不能越过其它金币。
如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候 (m) 枚金币恰好落在最左侧的 (m) 个格子中），则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢？
输入格式
输入仅有一行并包含两个正整数，依次为 (n) 和 (m) ，如题目所述。
输出格式
输出一个整数，表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。由于答案可能很大，请输出关于 (10^9+9) 取模后的值。
题解
首先不难发现，把金币向左移改成向右移是没有区别的
然后把题目看作是(m)枚金币把(n-m)个空位分成了(m+1)个部分(编号从(0sim m))，那么每次把第(i)枚硬币向右移动就相当于是把若干个空位从第(i)部分移动到了第(i-1)部分
然后这显然是一个阶梯(nim)模型，即每次可以选择一个(i eq 0)，将若干个物品从第(i)堆移到第(i-1)堆
我们其实不用管(m)枚金币具体在哪些位置，所以我们现在需要解决的问题是：将(n-m)个物品分成编号从(0sim m)的(m+1)堆，要求所有奇数堆的异或和不为(0)，有多少种方案？
容斥一下，可以用总方案数减去奇数堆异或和为(0)的方案数
设(dp[i][j])表示所有奇数堆的二进制前(i)位的异或和为0，共用了(j)个物品的方案数
在二进制的每一位上，为了异或和为(0)，必须要放偶数个(1)
假设(m+1)堆中有(a)个奇数堆，(b)个偶数堆，
那么转移方程为：(dp[i][j]=sumlimits_{k\%2=0} dp[i-1][j-k*2^{i-1}] * C(a, k))
表示在第(i)位上放(k)个1，所以在(a)个奇数位上任选(k)个放上1
然后填好所有奇数堆后，剩下的没有用到的物品就可以用插板法随意地分到偶数堆里
时间复杂度(O(nmlog n))，但是实际上跑得很快
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}
const ll mod = 1000000009;
ll fac[150005], invf[150005], dp[21][150005], ans; // 放了二进制前i位 用了j个物品
int n, m, l;
inline ll fpow(ll x, ll t) {
ll ret = 1;
for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
return ret;
}
inline ll C(ll _n, ll _m) {
return fac[_n] * invf[_m] % mod * invf[_n - _m] % mod;
}
void init() {
fac[0] = invf[0] = 1;
for (int i = 1; i <= 150000; i++) {
fac[i] = fac[i-1] * i % mod;
}
invf[150000] = fpow(fac[150000], mod-2);
for (int i = 149999; i; i--) {
invf[i] = invf[i + 1] * (i + 1) % mod;
}
}
int main() {
read(n); read(m);
n -= m;
init();
int tmp = 1; while (tmp <= n) { l++; tmp <<= 1; }
int a = (m + 1) / 2, b = (m + 2) / 2;
dp[0][0] = 1;
for (int i = 0; i < l; i++) {
for (int j = 0; j <= n; j++) {
if (!dp[i][j]) continue;
for (int k = 0; k <= a && k * (1 << i) + j <= n; k += 2) {
dp[i+1][j+k*(1<<i)] = (dp[i+1][j+k*(1<<i)] + dp[i][j] * C(a, k)) % mod;
}
}
}
for (int i = 0; i <= n; i++) {
ans = (ans + dp[l][i] * C((n-i) + b - 1, b - 1) % mod) % mod;
}
ans = (C(n+m, m) - ans + mod) % mod;
printf("%lld
", ans);
return 0;
}