卡特兰数 + 质因数分解

题目描述

我们称一个长度为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 的合法栈操作序列个数 / 出栈序列个数

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

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

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

怎么办？

分解质因数。

注意到

分数上下消一消

然后记 表示在答案中，编号为 的质数被乘了几次，
也就是把 进行唯一分解放到一个数组里

怎么求 ？

直接上代码：

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;
}