【题解】洛谷P3200 [HNOI2009] 有趣的数列（卡特兰数+质因数分解）

洛谷P3200：https://www.luogu.org/problemnew/show/P3200

思路

这题明显是卡特兰数的题型咯

一看精度有点大

如果递推卡特兰数公式要到O(n²)

可以证明得出分子可以把分母约到只剩1

那我们就可以用分解质因数的方法 把分子分母全都质因数分解

再把分母约掉 就可以直接把分子剩下的质因数乘起来即可

代码

#include<iostream> #include<cstdio> using namespace std; #define ll long long #define maxn 200000020 ll n,P,ans=1; int p[maxn/10],v[maxn/10],z[maxn]; void primes(ll n) { ll k=0; for(ll i=2;i<=n;i++) { if(!v[i]) { v[i]=i; p[++k]=i; } for(ll j=1;j<=k;j++) { if(p[j]>v[i]||p[j]*i>n) break; v[i*p[j]]=p[j]; } } } ll quickpow(ll a,ll b) { ll ret=1; while(b) { if(b%2==1) ret=ret*a%P; a=a*a%P; b/=2; } return ret; } int main() { scanf("%lld%lld",&n,&P); primes(2*n);//建立素数表和每个数的最小因子 for(ll i=2*n;i>=n+2;i--)//把分子质因数分解 { ll k=i; while(k>1) { z[v[k]]++;//这个质数的指数加1 k/=v[k]; } } for(ll i=2;i<=n;i++)//把分母质因数分解 { ll k=i; while(k>1) { z[v[k]]--;//约掉分子分母相同的质数 k/=v[k]; } } for(ll i=2;i<=2*n;i++) ans=(ans*quickpow(i,z[i]))%P;//把剩下的所有数相乘 printf("%lld",ans); } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9695485.html

相关资源：JAVA上百实例源码以及开源项目