[BZOJ 1856][SCOI 2010] 字符串

题目大意

\(n\)\(1\)\(m\)\(0\) 组成字符串,要求在组成的字符串中,在任意的前 \(k\) 个字符中,\(1\) 的个数不能少于 \(0\) 的个数。求可能的字符串数,对 \(20100403\) 取模。

\(1 \leqslant n, \; m \leqslant 1,000,000\)

题目链接

BZOJ 1856

CodeVS 2418

题解

将问题进行转化,对于每一位,若下一位选 \(1\),则向相对其 \((1, \; 1)\) 的位置移动,选 \(0\) 则向 \((1, \; -1)\) 移动,所求即从 \((0, \; 0)\) 移动到 \((n + m, \; n - m)\) 且不跨过 \(y = 0\)(该直线上可以)的方案数。

不考虑限制,答案是 \(\binom{n + m}{n}\)。所有跨过 \(y = 0\) 的方案都会经过 \(y = -1\),对这些方案,相当于从 \((0, \; -2)\)(原起点关于 \(y = -1\) 的对称点)到 \((n + m, \; n - m)\) 的方案数,为 \(\binom{n + m}{n + 1}\)

故,最终答案为: \[ \binom{n + m}{n} - \binom{n + m}{n + 1} = \frac{(n + m)!}{n! \times m!} \times \frac{n - m + 1}{n + 1} \]\(m = n\) 时,答案即为对应项的卡特兰数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
const int MOD = 20100403;
long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}
long long inv(long long a) {
return pow(a, MOD - 2);
}
long long fact(long long a) {
long long res = 1;
for (int i = 1; i <= a; i++) res = res * i % MOD;
return res;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
printf("%lld\n", fact(n + m) * inv(fact(m)) % MOD * inv(fact(n)) % MOD
* (n - m + 1) % MOD * inv(n + 1) % MOD);
return 0;
}