卡特兰数高精求调
查看原帖
卡特兰数高精求调
1121995
2021zjhs005楼主2024/3/8 17:37

rt,代码如下,感觉没什么问题:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}

const int N=1e5+10;

struct BigInt{
    int len,a[N];
    BigInt(){len=1;memset(a,0ll,sizeof(a));}
    BigInt(int x){while(x) a[++len]=x%10,x/=10;}
};
BigInt ss,t;
char s[N];

inline BigInt read_BigInt(){
    BigInt ret;
    scanf("%s",s+1);
    ret.len=strlen(s+1);
    for(int i=ret.len;i>=1;i--) ret.a[i]=s[ret.len-i+1]-(int)'0';
    return ret;
}
inline void print_BigInt(const BigInt ret){
    for(int i=ret.len;i>=1;i--)
        printf("%lld",ret.a[i]);
    putchar('\n');
}
inline BigInt operator + (const BigInt &x,const BigInt &y){
    BigInt ret;
    ret.len=max(x.len,y.len)+1;
    int up=0;
    for(int i=1;i<=ret.len;i++)   
    {
        ret.a[i]=(up+x.a[i]+y.a[i]);
        up=ret.a[i]/10;
        ret.a[i]%=10;
    }
    while(ret.len>1&&!ret.a[ret.len]) ret.len--;
    return ret;
}
inline BigInt operator - (const BigInt &x,const BigInt &y){
  BigInt ret;
  ret.len=max(x.len,y.len)+1;
  rep(i,1,ret.len){
    ret.a[i]=x.a[i]-y.a[i];
    if(ret.a[i]<0) ret.a[i+1]--,ret.a[i]+=10;
  }
  while(ret.len>1&&!ret.a[ret.len]) ret.len--;
  return ret;
}

inline BigInt operator / (const BigInt &x,const int &y){
    BigInt ret; ret.len=x.len;
    int down=0ll;
    for(int i=ret.len;i>=1;i--){
        ret.a[i]=(down*10+x.a[i])/y;
        down=(down*10+x.a[i])%y;
    }
    while(ret.len>1&&!ret.a[ret.len]) ret.len--;
    return ret;
}
inline BigInt operator * (const BigInt &x,const BigInt &y){
    BigInt ret; ret.len=x.len+y.len;
    for(int i=1;i<=x.len;i++)   
        for(int j=1;j<=y.len;j++)   
            ret.a[i+j-1]+=x.a[i]*y.a[j];
    int up=0;
    for(int i=1;i<=ret.len;i++)
    {
        ret.a[i]+=up;
        up=ret.a[i]/10;
        ret.a[i]%=10;
    }
    while(ret.len>1&&!ret.a[ret.len]) ret.len--;
    return ret;
}

inline BigInt Catlan(int n){
  if(n<2) return 1;
  return Catlan (n-1) * (4 * n - 2) / (n + 1);
}
signed main(){
  int x=read();
  print_BigInt(Catlan(x));
	return 0;
}
2024/3/8 17:37
加载中...