[Luogu P3200] [BZOJ 1485] [HNOI2009]有趣的数列

洛谷传送门

BZOJ传送门

题目描述

我们称一个长度为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的值。

输入输出样例

输入样例#1：

3 10

输出样例#1：

5

解题分析

先画一个图， 大概是这个样子的：

1 → 3 → 5....
↓   ↓   ↓....
2 → 4 → 6....

然后发现可以把第一行的视为左括号， 第二行视为右括号即可。 于是就是一个卡特兰数。

发现模数很大， 但n相对较小， 所以直接对阶乘分解质因数， 最后快速幂。总复杂度O(nlog(n))

代码如下：

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 2005000
#define MP 150050
int n, mod, pcnt;
int pri[MP], up[MP], down1[MP], down2[MP], dat[MX];
bool npr[MX];
IN int fpow(R int  , R int tim)
{
	int ret = 1;
	W (tim)
	{
		if (tim & 1) ret = 1ll * ret *   % mod;
		  = 1ll *   *   % mod, tim >>= 1;
	}
	return ret;
}
void sieve()
{
	R int i, j, tar;
	long long k;
	for (i = 2; i <= 2e6; ++i)
	{
		if (!npr[i]) pri[++pcnt] = i;
		for (j = 1; j <= pcnt; ++j)
		{
			tar = i * pri[j];
			if (tar > 2e6) break;
			npr[tar] = true;
			if (!(i % pri[j])) break;
		}
	}
	for (i = 1; i <= pcnt; ++i)
	for (k = pri[i]; k <= 2e6; k = k * pri[i]) dat[k] = i;
}
IN void solve(R int bd, int *res)
{
	for (R int i = 1; i <= bd; ++i) if (dat[i])
	res[dat[i]] += bd / i;
}
IN int C(R int n, R int m)
{
	int ret = 1;
	std::memset(up, 0, sizeof(up));
	std::memset(down1, 0, sizeof(down1));
	std::memset(down2, 0, sizeof(down2));
	solve(n, up), solve(m, down1), solve(n - m, down2);
	for (R int i = 1; i <= pcnt; ++i) ret = 1ll * ret * fpow(pri[i], up[i] - down1[i] - down2[i]) % mod;
	return ret;
}
int main(void)
{
	scanf(\"%d%d\", &n, &mod); sieve();
	printf(\"%d\", (C(2 * n, n) - C(2 * n, n - 1) + mod) % mod);
}