这题刚开始自己做的时候不太好理解,就发篇题解吧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!)

图片说明