[AGC040F] Two Pieces

太神仙了,看 sol 了。

做法

先规定当两个石子距离为 \(1\) 时,不能移动坐标小的石子。这样就只需要对操作序列计数了。

考虑对有 \(K\) 个把某个石子的坐标增加 \(1\) 的操作的方案计数。\(K = N\) 的情况很容易单独考虑。

对于 \(K < N\) 的情况,假设我们已经确定了把某个石子的坐标增加 \(1\) 的操作,考虑一个序列 \(s\),若第 \(i\) 个把某石子坐标 \(+1\) 操作移动的是坐标小的石子,\(s_i = -1\),否则 \(s_i = 1\)。这样的一个序列 \(s\) 显然满足 \(\forall 1 \le i \le K, \sum_{k=1}^i s_i > 0\)。对于一个这样的序列 \(s\),我们来考虑有多少种把“坐标小的石子移动到坐标大的石子的位置”的操作插入到这个(只包含把某石子坐标增加 \(1\) 的操作的)操作序列之中的方案。显然 \(s\) 中有 \(B\)\(1\)\(K-B\)\(-1\)。如果最后一个插入的操作插在 \(s_i\) 对应的操作和 \(s_{i+1}\) 对应的操作之间,那么 \(\sum_{k \le i} [s_k = 1]+\sum_{k > i} [s_k = -1] = B-(\sum_{k > i} s_k) = A\)。设 \(t_i = \sum_{k \le i} s_k\)。如果有一个操作被插入在 \(s_i\)\(s_{i+1}\) 对应的操作之间,且存在 \(j > i\)\(t_j \le t_i\),那么这个操作序列一定不合法。所以最后一个插入的操作一定在 \(t_i = B-(K-B)-(B-A)=B+A-K\) 的最后一个 \(s_i\)\(s_{i+1}\) 之间,其他操作必须插入最后一个 \(t_i = x, x \le B+A-K\) 的最后一个 \(s_i\)\(s_{i+1}\) 之间,且只要满足这个条件得到的就是一个合法的操作序列。于是问题就变成了求把 \(N-K-1\) 拆成 \(B+A-K+1\) 个非负整数之和的方案数,这很容易用一个组合数计算。注意到对于不同的 \(s\),插入操作的方案之和 \(K\) 有关,所以我们枚举 \(K\) 统计答案即可。

对于一个对应的 \(K\),计算对应的 \(s\) 的个数是一个类似卡特兰数的问题,不会的话可以去看看 AGC021E。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10000010;
const int mod = 998244353;

int N, A, B, ans;
int fac[maxn << 1], ifac[maxn << 1], inv[maxn << 1];

int binom(int x, int y) {
if (x < 0 || y < 0) return 0;
if (y > x) return 0;
return 1LL * fac[x] * ifac[y] % mod * ifac[x-y] % mod;
}

int cal(int X, int Y) {
return 1LL * (X - Y + 1) * inv[X + 1] % mod * binom(X+Y, X) % mod;
}

int main() {
scanf("%d%d%d", &N, &A, &B);
if (!B) {
puts("1");
return 0;
}
fac[0] = ifac[0] = 1, inv[1] = 1;
for (int i = 2; i <= N * 2; i++) {
inv[i] = mod - 1LL * inv[mod % i] * (mod / i) % mod;
}
for (int i = 1; i <= N * 2; i++) {
fac[i] = 1LL * fac[i-1] * i % mod;
ifac[i] = 1LL * ifac[i-1] * inv[i] % mod;
}
if (A != B && A + B == N) {
ans = cal(B-1, A);
}
for (int K = B; K < N; K++) {
int v1 = 0, v2 = 0;
v1 = cal(B-1, K-B);
v2 = binom(N-K-1+B+A-K+1-1, B+A-K+1-1);
ans = (ans + 1LL * v1 * v2 % mod) % mod;
}
printf("%d\n", ans);
return 0;
}