洛谷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。

輸出#

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

輸入範例 1#

3 10

輸出範例 1#

輸入範例 2#

10 1013

輸出範例 2#

輸入範例 3#

675546 14358205

輸出範例 3#

提示#

对于样例 1：对应的 5 个有趣的数列分别为

（1,2,3,4,5,6），（1,2,3,5,4,6），（1,3,2,4,5,6），（1,3,2,5,4,6），（1,4,2,5,3,6）。

50% 的数据满足 n≤1000 ，100% 的数据满足 n≤1000000 且 P≤1000000000。

思路#

首先发现它是个卡特兰数

硬算前几项的数字规律（我是这样做的）
可以转换为一个典型的卡特兰数的例子：

n 个数排成两行，使右边都大于左边，后边都大于前边，求排法数量

将奇数看成第一行，将偶数看成第二行即可。

然后发现数据很大，递推式都有除法，p 也不是质数不能用逆元（~~虽然我也不回逆元我太弱了~~）

所以要用这个通项式

f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1}

化一下

f(n)=\frac{C\begin{matrix} n\\ 2n \end{matrix}}{n+1} \\ =\frac{(2n)!}{n!\cdot n!\cdot (n+1)}\\ =\frac{(2n)!}{n!\cdot (n+1)!}

这样化的作用是可以用特殊的方法约分

枚举 1~2n 的所有素数

然后分别计算 $n,(n+1),2n$ 中那个素数的次数(cnt1,cnt2,cnt3)

再往答案中加乘上 $primes_i^{(cnt3-cnt2-cnt1)}$ 就好了

注意这里是乘不是加我就是这样错的

Code#

//I closed myself.What a happy zero-boomed contest!!!
//上一行是考试自闭的时候写的不要管
//(2n)!/(n!*n!*(n+1))
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL MAXN=1000000+5;

LL n,p,cnt;
bool v[MAXN];
LL primes[2*MAXN];
bool isHeshu[2*MAXN];

LL oula(LL x);//质数筛
LL qkpow(LL x,LL y);//快速幂

int main(){
//	freopen("LLeresting.in","r",stdin);
//	freopen("LLeresting.out","w",stdout);
	
	scanf("%d%d",&n,&p);
	oula(2*n);
	LL ans=1;
	for(LL i=1;i<=cnt;++i){
		LL cnt1=0,cnt2=0,cnt3=0;
		LL pm=primes[i];
		while(pm<=2*n){
			cnt1+=n/pm;
			cnt2+=(n+1)/pm;
			cnt3+=2*n/pm;
			pm*=primes[i];//当前质因子次数+1
		}
		LL sl=cnt3-cnt1-cnt2;
		ans*=qkpow(primes[i],sl);
		ans%=p;
	}
	printf("%lld\n",ans);
	
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

LL oula(LL x){
	for(LL i=2;i<=x;++i){
		if(!isHeshu[i]){
			primes[++cnt]=i;
		}
		for(LL j=1;primes[j]*i<=x;++j){
			isHeshu[primes[j]*i]=1;
			if(i%primes[j]==0)break;
		}
	}
}

LL qkpow(LL x,LL y){
	LL sum=x;
	LL ret=1;
	while(y){
		if(y&1){
			ret=ret*sum%p;
		}
		sum=sum*sum%p;
		y>>=1;
	}
	return ret;
}