题目链接
将$n$个$1$和$m$个$0$组成字符串，使得在任意的前$k$个字符中，$1$的个数不能少于$0$的个数。求满足条件的字符串共有多少个。
$1\le m \le n \le 1000000$
本题是卡特兰数的一个简单变式。
回忆卡特兰数的推导过程，可以生成的所有字符串共有$C_{n+m}^n$个，其中不合法的字符串有$C_{n+m}^{n+1}$个。最终答案即为$C_{n+m}^{n}-C_{n+m}^{n+1}$。计算组合数前须预处理出阶乘逆元。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 20100403;
int N, M;
int inv[2000005], fac[2000005], facinv[2000005];
int C(int n, int m) {
return (ll) fac[n] * facinv[m] % p * facinv[n - m] % p;
}
int main() {
cin >> N >> M;
inv[1] = 1; fac[0] = fac[1] = 1; facinv[1] = 1;
for (register int i = 2; i <= N + M; ++i) {
inv[i] = (ll) (p - p / i) * inv[p % i] % p;
fac[i] = (ll) i * fac[i - 1] % p;
facinv[i] = (ll) facinv[i - 1] * inv[i] % p;
}
cout << (C(N + M, N) - C(N + M, N + 1) + p) % p;
return 0;
}
|