洛谷P2490 [SDOI2011] 黑白棋 题解
题目链接:P2490 [SDOI2011] 黑白棋
题意:
小 A 和小 B 又想到了一个新的游戏。
这个游戏是在一个 $1 \times n$ 的棋盘上进行的,棋盘上有 $k$ 个棋子,一半是黑色,一半是白色。
最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。
小 A 可以移动白色棋子,小 B 可以移动黑色的棋子,其中白色不能往左,黑色不能往右。他们每次操作可以移动 $1$ 到 $d$ 个棋子。
每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。
小 A 和小 B 轮流操作,现在小 A 先移动,有多少种初始棋子的布局会使他胜利呢?
输入格式:
输入三个数 $n,k,d$。
输出格式:
输出小 A 胜利的方案总数。答案对 $10^9+7$ 取模。
数据范围:
保证 $1 \leq d \leq k \leq n \leq 10^4$,$k$ 为偶数,$k \leq 100$。
由于终止状态一定是 “……黑白…黑白…黑白……” 的情况
所以我们可以把相邻两个黑白棋子的距离看作一堆石子,那么问题就转化为了一个 K–Nim 游戏
确切的讲,是一个 $d$–Nim游戏,因为每次可以操作不超过 $d$ 堆石子。
记 $b_s = \sum_{i=1}^n\left(a_i\right)_s$ ,其中 $(x)_s$ 表示 $x$ 二进制下第 $s$ 位。
因为 $d$–Nim 先手必胜的条件是存在一个 $s$ 满足 $b_s\not\equiv 0 \pmod{d+1}$ ,所以问题转化为找这样的情况数。
正难则反。考虑设 $f(i,j)$ 表示前 $i$ 位(记 $0$ 到 $i-1$ 位)中 $b_j\equiv 0 \pmod{d+1}$ 。
转移考虑枚举第 $i$ 位中选出 $x(d+1)$ 堆为 $1$ 的,有
这里 $\uparrow$ 表示 a += b
。记 $c~(c \ge 0)$ 为最高位,那么答案就是
时间复杂度 $\mathcal{O}(n \log n \log_d n)$ ,可能还有更紧的上界不过已经足够小了。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
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)(1e4 + 15))
int dp[15][N], C[N][233];
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, k, d; cin >> n >> k >> d;
rep(i, 0, n) C[i][0] = 1;
rep(i, 1, n) rep(j, 1, min(i, k)) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
dp[0][0] = 1;
rep(i, 0, 12) rep(j, 0, n - k)
{
const int now = 1ll << i;
for(int x = 0; j + now * x * (d + 1) <= n - k && x * (d + 1) <= k / 2; x++)
add(dp[i + 1][j + now * x * (d + 1)], dp[i][j] * C[k / 2][x * (d + 1)] % mod);
}
int res = 0;
rep(i, 0, n - k) add(res, dp[13][i] * C[n - i - k / 2][k / 2] % mod);
cout << (C[n][k] + mod - res) % mod << '\n';
return 0;
}
参考文献: