P3200 [HNOI2009]有趣的数列

**首先，这是一个标准的卡特兰数** 问题是要取模 就不能直接套用公式了 因为卡特兰数的分子分母可以整除 所以质因数分解 线性筛预处理出$2*n$范围内的质数以及每个数的最小质因子 将合数拆分，用加法原理算出每个质数的指数 然后枚举质数用快速幂求解即可。 ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=2e6+5; int n,p,prime[N/10],mi[N],cnt,num[N]; ll ans=1; ll quickpow(ll n,ll k) { ll s=1; while (k) { if (k&1) s=s*n%p; n=n*n%p; k>>=1; } return s; } int main() { scanf("%d%d",&n,&p); for (int i=2;i<=n*2;i++) { if (!mi[i]) mi[i]=prime[++cnt]=i; for (int j=1;j<=cnt&&i*prime[j]<=2*n;j++) { mi[i*prime[j]]=prime[j]; if (i%prime[j]==0) break; } } for (int i=1;i<=n;i++) num[i]=-1; for (int i=n+2;i<=n*2;i++) num[i]=1; for (int i=n*2;i>1;i--) if (mi[i]<i) num[mi[i]]+=num[i],num[i/mi[i]]+=num[i]; for (int i=2;i<=2*n;i++) if (mi[i]==i) ans=ans*quickpow(mi[i],num[i])%p; printf("%lld\n",ans); return 0; } ```