题目描述
一个 \(1\times n\) 的棋盘上最初摆放有 \(m\) 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。
Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作，且 Alice 先行。当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。金币不能被移出棋盘，也不能越过其它金币。
如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候 \(m\) 枚金币恰好落在最左侧的 \(m\) 个格子中），则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢？
输入格式
输入仅有一行并包含两个正整数，依次为 \(n\) 和 \(m\) ，如题目所述。
输出格式
输出一个整数，表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。由于答案可能很大，请输出关于 \(10^9+9\) 取模后的值。
题解
首先不难发现，把金币向左移改成向右移是没有区别的
然后把题目看作是\(m\)枚金币把\(n-m\)个空位分成了\(m+1\)个部分(编号从\(0\sim m\))，那么每次把第\(i\)枚硬币向右移动就相当于是把若干个空位从第\(i\)部分移动到了第\(i-1\)部分
然后这显然是一个阶梯\(nim\)模型，即每次可以选择一个\(i\neq 0\)，将若干个物品从第\(i\)堆移到第\(i-1\)堆
我们其实不用管\(m\)枚金币具体在哪些位置，所以我们现在需要解决的问题是：将\(n-m\)个物品分成编号从\(0\sim m\)的\(m+1\)堆，要求所有奇数堆的异或和不为\(0\)，有多少种方案？
容斥一下，可以用总方案数减去奇数堆异或和为\(0\)的方案数
设\(dp[i][j]\)表示所有奇数堆的二进制前\(i\)位的异或和为0，共用了\(j\)个物品的方案数
在二进制的每一位上，为了异或和为\(0\)，必须要放偶数个\(1\)
假设\(m+1\)堆中有\(a\)个奇数堆，\(b\)个偶数堆，
那么转移方程为：\(dp[i][j]=\sum\limits_{k\%2=0} dp[i-1][j-k*2^{i-1}] * C(a, k)\)
表示在第\(i\)位上放\(k\)个1，所以在\(a\)个奇数位上任选\(k\)个放上1
然后填好所有奇数堆后，剩下的没有用到的物品就可以用插板法随意地分到偶数堆里
时间复杂度\(O(nm\log 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\n", ans);
return 0;
}