洛谷P3200《[HNOI2009]有趣的数列》

卡特兰数 + 质因数分解

题目描述

我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件:

(1)它是从1到2n共2n个整数的一个排列{ai};

(2)所有的奇数项满足a1<a3<…<a2n-1,所有的偶数项满足a2<a4<…<a2n;

(3)任意相邻的两项a2i-1与a2i(1<=i<=n)满足奇数项小于偶数项,即:a2i-1<a2i。

现在的任务是:对于给定的n,请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod P的值。

输入格式

输入文件只包含用空格隔开的两个整数n和P。输入数据保证,50%的数据满足n<=1000,100%的数据满足n<=1000000且P<=1000000000。

输出格式

仅含一个整数,表示不同的长度为2n的有趣的数列个数mod P的值。

解析

首先给出结论:卡特兰数。


注意到偶数位的数字必须大于前面偶数位、偶数位必须大于奇数位两个性质,可以得出这个结论:

对于任意偶数位的数字,都满足该数字大于前面的所有数字

考虑把偶数位、奇数位拆出来看,即拆成一个两行 n 列的矩阵,第一行表示奇数位,第二行表示偶数位。
上面的式子可以写成:

对于任意在第二行的数字,都满足它大于它左边、左上边(不含正上方)的所有数字

把第一排的数字都记为 0,第二排的数字都记为 1,放回到原序列,再联系前面的结论,可以得出:

在(更新为 0 或 1 的)原序列中,对于任意一位 0,都满足前面的所有 0 的个数不小于前面所有 1 的个数;对于任意一位 1,都满足前面的所有 0 的个数大于前面所有 1 的个数

如果把 0 看作栈的入栈操作,1 看作栈的出栈操作,那么上面的式子可以写成:

在一个栈操作序列中,对于任意一个入栈操作,都满足前面的入栈操作数不小于前面的出栈操作数;对于任意一个出栈操作,都满足前面的入栈操作数大于前面的出栈操作数

也就是求 长度为 n 的合法栈操作序列个数 / 出栈序列个数

这个怎么求我不用再多说了吧


接下来是另一个问题:取模

题目的 $p$ 是读入的,样例就明明白白的说了不一定是质数,甚至还可能很小

怎么办?

分解质因数。

注意到

分数上下消一消

然后记 $f_i(i \in \text{Primes})$ 表示在答案中,编号为 $i$ 的质数被乘了几次,
也就是把 $ans$ 进行唯一分解放到一个数组里

怎么求 $f$ ?

直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 在线性筛中,如果 i 这个数是被第 k 个质数筛掉的,那么 sieveBy[i] = k
// prs[i] 表示第 i 个质数

for (int i = n + 2; i <= 2 * n; ++i) {
// 加上分子 n + 2 到 2n 的乘积的分解
int x = i;
while (x > 1) {
// 分解质因数
++f[sieveBy[x]];
x = x / prs[sieveBy[x]];
}
}
for (int i = 2; i <= n; ++i) {
// 消去分母中 1 到 n 的乘积的分解
int x = i;
while (x > 1) {
--f[sieveBy[x]];
x = x / prs[sieveBy[x]];
}
}

最后 for 一遍所有的质数,快速幂乘一下就好了

代码实现

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>

bool notprime[2000000 + 10];
int prs[2000000 + 10], cnt;
int sieveBy[2000000 + 10];
int n, p;
int calcs[2000000 + 10];

int fastPow(int a, int b, int p) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * 1ll * a % p;
a = 1ll * a * 1ll * a % p;
b >>= 1;
}
return ret;
}

void sieve() {
notprime[0] = notprime[1] = true;
for (int i = 2; i <= 2 * n; ++i) {
if (!notprime[i]) {
prs[++cnt] = i;
sieveBy[i] = cnt;
}
for (int j = 1; j <= cnt && i * prs[j] <= 2 * n; ++j) {
notprime[i * prs[j]] = true;
sieveBy[i * prs[j]] = j;
}
}
}

int main() {
scanf("%d %d", &n, &p);
sieve();
// ans = ((2n)! / (n! * n!) * (n + 1))
// = ((1 * 2 * ... * (n - 1) * n * (n + 1) * (n + 2) * (n + 3) * ... * 2n) /
// (1 * 2 * ... * (n - 1) * n) * (1 * 2 * ... * (n - 1) * n) * (n + 1))
// = ((n + 1) * (n + 2) * (n + 3) * ... * 2n) /
// ((1 * 2 * ... * (n - 1) * n) * (n + 1))
// = ((n + 2) * (n + 3) * ... * 2n) / ((1 * 2 * ... * (n - 1) * n)
for (int i = n + 2; i <= 2 * n; ++i) {
int x = i;
while (x > 1) {
// printf("Now exting: %d\n", x);
++calcs[sieveBy[x]];
x = x / prs[sieveBy[x]];
}
}
// printf("Calc 1.\n");
for (int i = 2; i <= n; ++i) {
int x = i;
while (x > 1) {
--calcs[sieveBy[x]];
x = x / prs[sieveBy[x]];
}
}
int ans = 1;
for (int i = 1; i <= cnt; ++i) {
ans = 1ll * ans * 1ll * fastPow(prs[i], calcs[i], p) % p;
}
printf("%d\n", ans);
return 0;
}