[SCOI 2010] 生成字符串

题目大意

nn11mm00 组成字符串,要求在组成的字符串中,在任意的前 kk 个字符中,11 的个数不能少于 00 的个数。求可能的字符串数,对 2010040320100403 取模。

1n,  m1,000,0001 \leqslant n, \; m \leqslant 1,000,000

题目链接

【SCOI 2010】生成字符串 - Luogu 1641

题解

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

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

故,最终答案为:

(n+mn)(n+mn+1)=(n+m)!n!×m!×nm+1n+1\binom{n + m}{n} - \binom{n + m}{n + 1} = \frac{(n + m)!}{n! \times m!} \times \frac{n - m + 1}{n + 1}

m=nm = 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;
}