题目传送门
因为所有奇数项是升序的，所以
又因为奇数项小于偶数项
所以每个偶数位都能插在所对应奇数项的后面，换一种说法，就是把2*n个数从小到大排好序，把奇数项和偶数项丢进去，使得每一个前缀，奇数项的个数都比偶数项多。
求Catalan数有4个公式。（点链接查看）
其中有两个组合数公式是在一起的。
那么前面两种很明显不行，第一种会超时，第二种因为p不是质数，求不了逆元，而且p也没有什么很好的性质。
那么组合数，为了简单，我们选取第一种，并且化简
很明显这个东西肯定是可以整除的。
所以，又不能求逆元，那么我们就分解质因数，然后上下抵消不就行了？
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; int n,p; int prime[2000010],mmin[2000010]; int t[2000010]; bool vis[2000010]; long long ksm(long long x,int t){ long long tot=1; while(t>=1){ if(t%2==1){ tot*=x; tot%=p; } x*=x; x%=p; t/=2; } return tot; } int main(){ scanf("%d %d",&n,&p); for(int i=2;i<=2*n;i++){ if(vis[i]==false) prime[++prime[0]]=i,mmin[i]=i; for(int j=1;j<=prime[0] && i*prime[j]<=2*n;j++){ vis[i*prime[j]]=true; mmin[i*prime[j]]=prime[j]; if(i%prime[j]==0) break; } } int x; for(int i=n+2;i<=2*n;i++){ x=i; while(x!=1) t[mmin[x]]++,x/=mmin[x]; } for(int i=2;i<=n;i++){ x=i; while(x!=1) t[mmin[x]]--,x/=mmin[x]; } long long ans=1; for(int i=1;i<=prime[0];i++){ ans=ans*ksm((long long)prime[i],t[prime[i]])%p; } printf("%lld\n",ans); }
