AK-dream

题目描述

一个 $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)$,但是实际上跑得很快

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}

 评论