这题刚开始自己做的时候不太好理解,就发篇题解吧qwq~
讲解的话可以看看这些题解,这里就给一下自己写的代码啦~
#include<cstdio> using namespace std; const int N=60005; const long long P=1000000000000;//压位高精度,压了12位 int n,len,primetot,p[N]; long long ans[15000]; bool v[N*2]; void mul(int x) {//高精度乘法 for (int i=1; i<=len; i++) ans[i]*=x; for (int i=1; i<=len; i++) ans[i+1]+=ans[i]/P,ans[i]%=P; if (ans[len+1]>0) len++; } int main() { scanf("%d",&n),ans[len=1]=1; for (int i=2; i<=n*2; i++) if (!v[i]) { p[++primetot]=i; for (int j=i; j<=n*2; j+=i) v[j]=1; }//筛素数 for (int i=1,cnt; i<=primetot; i++) { cnt=0; for (int x=p[i]; x<=n*2; x*=p[i]) cnt+=n*2/x-n/x-(n+1)/x; //【前置知识:阶乘分解】 //见下面的公式,通过分解质因数对分子分母进行约分,避免高精度除法 while(cnt--) mul(p[i]); } printf("%lld",ans[len]); for (int i=len-1; i; i--) printf("%012lld",ans[i]);//“%012”是输出12位并补齐前导零 } //Catalan(n)=C(2n,n)-C(2n,n-1)=(2n)!/((n+1)!*n!)