洛谷P5363 [SDOI2019] 移动金币 题解
题意:
Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作,且 Alice 先行。
当轮到一个玩家的时候,他可以选择一枚金币,并将其向左移动任意多格,且至少移动一格。金币不能被移出棋盘,也不能越过其它金币。
一个 \(1\times n\) 的棋盘上最初摆放有 \(m\) 枚金币。其中每一枚金币占据了一个独立的格子,任意一个格子内最多只有一枚金币。
如果轮到一个玩家的时候他已经无法做出任何有效操作了(显然这个时候 \(m\) 枚金币恰好落在最左侧的 \(m\) 个格子中),则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人,他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢?
输入格式:
输入仅有一行并包含两个正整数,依次为 \(n\) 和 \(m\),如题目所述。
输出格式:
输出一个整数,表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。
由于答案可能很大,请输出关于 \(10^9+9\) 取模后的值。
数据范围:
\(1\le n\le 1.5\times 10^5\) 且 \(1\le m\le 50\)。
考虑如何判断一个状态是否为先手必胜态 \(\rm N\) 。
记 \(x_i\) 为每个棋子的位置,并记 \(b_i = x_i - x_{i-1}-1\) 为每个棋子初始可以移动的格数。
注意到当第 \(i\) 个金币移动 \(x\) 格时,会使得 \(b_i \gets b_i - x\) 且 \(b_{i + 1} \gets b_{i + 1} + x\) 。
于是这就变成了一个反着的阶梯博弈,也就是从 \(m + 1\) 开始的阶梯博弈,参考 P3480 题解 。
阶梯博弈的结论是,先手为 \(\rm N/P\) 取决与奇数堆的 Nim 游戏是什么。
本题因为是反过来的,所以先手为必败态 \(\rm P\) 当且仅当 \(n,\,n-2,\,\cdots\) 这些位置满足异或和为 \(0\) 。
如果求出有多少个状态为 \(\rm P\) ,那么用总数减去 \(\rm P\) 的状态数就是答案了。
现在问题就变成了将 \(n\) 个格子放进 \(m+1\) 个盒子里,盒子可空,且与 \(m + 1\) 奇偶性相同的盒子异或和为 \(0\) 。
这个异或和不太好直接搞,套路地考虑枚举二进制下每一位 \(2^i\) ,每次我们会放偶数个这样的位。
考虑设 \(f(i,j)\) 为考虑前 \(i\) 位(从低到高),还剩 \(j\) 个格子没放到盒子里时状态为 \(\rm P\) 的方案数。那么 \[ f(i,j) = \sum_{k\ \mathrm{is\ even}} \binom{\left\lfloor\frac{m+1}{2}\right\rfloor}{k}f(i + 1,j - k\cdot 2^i) \] 其中 \(\left\lfloor\frac{m+1}{2}\right\rfloor\) 是盒子的个数。
这样子还可能有剩余的格子没有塞到盒子里。考虑插板法塞到与 \(m+1\) 奇偶性不同的位置,那么 \[ \mathrm{Ans} = \binom{n}{m} - \sum_{i=0}^{n - m}\binom{i + \left\lfloor\frac{m+1}{2}\right\rfloor - 1}{\left\lfloor\frac{m+1}{2}\right\rfloor -1}f(i,0) \] 时间复杂度 \(\mathcal{O}(nm \log n)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
int res, lg[N], fac[N], infac[N], f[21][N];
int qpow(int a, int b)
{
int r = 1;
for(a %= mod; b; b >>= 1, a = a * a % mod)
if(b & 1) r = r * a % mod;
return r;
}
int C(int n, int m)
{
if(n < m || m < 0) return 0;
return fac[n] * infac[n - m] % mod * infac[m] % mod;
}
void init(int n)
{
fac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
infac[n] = qpow(fac[n], mod - 2);
Rep(i, n - 1, 0) infac[i] = infac[i + 1] * (i + 1) % mod;
rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, m; cin >> n >> m; if(n < m) return cout << "0\n", 0;
init(n + m + 5); ; f[lg[n] + 1][n - m] = 1;
Rep(i, lg[n], 0) rep(j, 0, n - m) if(f[i + 1][j])
for(int k = 0; k <= (m + 1) / 2 && k * (1ll << i) <= j; k += 2)
add(f[i][j - k * (1ll << i)], f[i + 1][j] * C((m + 1) / 2, k) % mod);
rep(i, 0, n - m) add(res, f[0][i] * C(i + (m + 2) / 2 - 1, (m + 2) / 2 - 1) % mod);
cout << (C(n, m) + mod - res) % mod << '\n';
return 0;
}
参考文献:
[1] https://www.luogu.com.cn/article/9f76q5ni
题外话:
放图片。