【BZOJ1485】[HNOI2009]有趣的数列（组合数学）

题面

BZOJ

洛谷

题解

从小往大填数，要么填在最小的奇数位置，要么填在最小的偶数位置。

偶数位置填的数的个数不能超过奇数位置填的数的个数。

好的，卡特兰数。

诶，woc，我不会卡特兰数啊。行，来学一下。

\(H(0)=H(1)=1\)

\(H(n)=\sum_{i=0}^{n-1} H(i)H(n-i-1)\)

\(H(n)=H(n-1)*\frac{4n-2}{n+1}\)

\(H(n)=\frac{C_{2n}^n}{n+1}=C_{2n}^n-C_{2n}^{n+1}\)

前几项是\(1,1,2,5,14,42,132......\)

我\(NOI\)的时候就因为不会卡特兰数少得了\(12\)分，菜死。

那么这题直接算分子分母两个部分的质因子，然后手动除一下再乘，这样与逆元无关了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 2000100

int n,P,ans=1;

int pri[MAX],a[MAX],tot;

bool zs[MAX];

void pre(int n)

{

	for(int i=2;i<=n;++i)

	{

		if(!zs[i])pri[++tot]=i;

		for(int j=1;j<=tot&&i*pri[j]<=n;++j)

		{

			zs[i*pri[j]]=true;

			if(i%pri[j]==0)break;

		}

	}

}

void Divide(int x,int w)

{

	for(int i=1;i<=tot&&pri[i]*pri[i]<=x;++i)

		while(x%pri[i]==0)x/=pri[i],a[pri[i]]+=w;

	if(x>1)a[x]+=w;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%P;a=1ll*a*a%P;b>>=1;}

	return s;

}

int main()

{

	scanf("%d%d",&n,&P);pre(n+n);Divide(n+1,-1);

	for(int i=n+n;i>n;--i)Divide(i,1);

	for(int i=n;i;--i)Divide(i,-1);

	for(int i=1;i<=n+n;++i)ans=1ll*ans*fpow(i,a[i])%P;

	printf("%d\n",ans);

	return 0;

}