题目描述

题面

思路

只是求卡特兰数的第n项,有通项公式
$$(n)=\frac {C_{2n}^{n}}{n+1}$$
注意要高精度,先分解质因数并约分,转化为乘法

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,f[120005],t[120005],len=1;
long long ans[36120],mt=1e13,tmp=1;
void ch(ll k){
    for (ll i=1;i<=len;++i) ans[i]*=k;
    for (ll i=1;i<=len;++i){
        if (ans[i]>9){
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
    }
    while (ans[len+1]){
        len++;
        ans[len+1]+=ans[len]/10;
        ans[len]%=10;
    }
}

void pr(){
    for (ll i=len;i>=1;--i) printf("%lld",ans[i]);
}

int main(){
    ans[1]=1;
    cin>>n;
    for (ll i=2;i<=n<<1;++i){
        if (f[i]!=0) continue;
        for (ll j=i+i;j<=n<<1;j+=i){
            f[j]=i;//标记因子
        }
    }
    for (ll i=n+2;i<=n<<1;++i){
        t[i]++;
    }
    for (ll i=2;i<=n;++i){
        t[i]--;
    }
    for (ll i=n<<1;i>=2;--i){
        if (f[i]==0) continue;
        if (t[i]==0) continue;
        ll tmp=f[i];
        t[tmp]+=t[i];
        t[i/tmp]+=t[i];
        t[i]=0;
    } //将指数推到质因数上
    for (ll i=2;i<=n<<1;++i){
        if (t[i]>0){
            while (t[i]){
                t[i]--;
                tmp*=i;
                if (tmp>=mt){  //这里缓冲一下,节约时间
                    ch(tmp); //高精乘法
                    tmp=1;
                }
            }
        }
    }
    ch(tmp);  //别忘了清空缓冲
    pr();
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/70/