有理由相信第100个Catalan数爆long long了
by 小粉兔 @ 2018-04-20 19:04:31
最好递推过程中就取模
by 咪嗷呜喵 @ 2018-07-18 20:32:34
@[VinylChloride](/space/show?uid=96554) 高精版你值得拥有
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100001;
struct bigint{
int length,num[maxn];
bigint(){
memset(num,0,sizeof(num));
length=0;
}
};
inline void change(char a[],bigint &b){
b.length=strlen(a);
for(int i=0;i<b.length;i++){
b.num[i]=a[b.length-i-1]-'0';
}
}
inline void add(bigint &a,bigint &b){
int ll=max(a.length,b.length);
int exd=0;
for(int i=0;i<ll;i++){
int tmp=a.num[i]+b.num[i]+exd;
a.num[i]=tmp%10;
exd=tmp/10;
}
a.length=ll;
if(exd){
a.num[ll]=exd;
a.length++;
}
}
inline void mul(bigint &a,int b){
for(int i=0;i<a.length;i++){
a.num[i]*=b;
}
for(int i=0;i<a.length;i++){
a.num[i+1]+=a.num[i]/10;
a.num[i]%=10;
}
int m=a.num[a.length];
while(m){
a.num[(++a.length)-1]=m%10;
m/=10;
}
}
inline void div(bigint &a,int b){
int d=0;
for(int i=a.length-1;i>=0;i--){
int tmp=d*10+a.num[i];
a.num[i]=tmp/b;
d=tmp%b;
}
while(a.num[a.length-1]==0){
a.length--;
}
}
inline int divm(bigint &a,int b){
int d=0;
for(int i=a.length-1;i>=0;i--){
int tmp=d*10+a.num[i];
a.num[i]=tmp/b;
d=tmp%b;
}
while(a.num[a.length-1]==0){
a.length--;
}
return d;
}
char s[maxn];
int main(){
scanf("%s",s);
if(s[0]=='1'&&strlen(s)==1){
printf("1");return 0;
}
int n=0;
for(int i=0;i<strlen(s);i++){
n=(n<<1)+(n<<3)+s[i]-'0';
}
bigint st1;
change(s,st1);
bigint ne;ne.num[0]=2;ne.length=1;
add(st1,ne);
bigint ans;
for(int i=n+3;i<=(n<<1);i++){
mul(st1,i);
}
for(int i=1;i<=n;i++){
div(st1,i);
}
int st2=divm(st1,100);
cout<<st2;
return 0;
}
```
by TLE自动机 @ 2019-06-10 11:23:39