Chtholly_is_cute @ 2023-09-20 20:08:31
code:
#include<bits/stdc++.h>
using namespace std;
struct bigint{
int len;
int a[5000];
};
void set1(bigint &a,bigint b){
a.len=b.len;
memset(a.a,0,sizeof(a.a));
for(int i=1;i<=a.len;i++){
a.a[i]=b.a[i];
}
}
void set2(bigint &a,int b){
a.len=0;
memset(a.a,0,sizeof(a.a));
while(b){
a.a[++a.len]=b%10;
b/=10;
}
}
void set3(bigint &a,string b){
a.len=b.size();
memset(a.a,0,sizeof(a.a));
for(int i=1;i<=a.len;i++){
a.a[i]=b[a.len-i]-'0';
}
}
void print(bigint k){
if(k.len==0){
cout<<0;
return;
}
for(int i=k.len;i>=1;i--){
cout<<k.a[i];
}
}
bigint add(bigint a,bigint b){
bigint res;
res.len=0;
int jw=0;
while(res.len<=a.len||res.len<=b.len){
res.a[++res.len]=a.a[res.len]+b.a[res.len]+jw;
jw=res.a[res.len]/10;
res.a[res.len]%=10;
}
res.a[++res.len]=jw;
while(res.len>=1&&res.a[res.len]==0)--res.len;
return res;
}
int main(){
int n;
cin>>n;
bigint a,b,c;
if(n==1)cout<<0;
else if(n==2)cout<<1;
else if(n==3)cout<<2;
else{
set2(a,1);
set2(b,2);
for(int i=3;i<=n;i++){
set1(c,add(a,b));
set1(a,b);
set1(b,c);
}
print(c);
}
}by PVZ__2 @ 2023-09-20 20:31:28
@andyzhu444
#include<bits/stdc++.h>
using namespace std;
char ans[5005][5005];
int main(){
int n;
cin>>n;
ans[0][0]='1';
ans[1][0]='1';
for (int i = 2; i <= n; i++){
int lens1 = strlen(ans[i - 1]);
int lens2 = strlen(ans[i - 2]);
char ans1[2005] = "";
char ans2[2005] = "";
for (int j = 0; j < lens1; j++)ans1[lens1 - j - 1] = ans[i - 1][j];
for (int j = 0; j < lens2; j++)ans2[lens2 - j - 1] = ans[i - 2][j];
int lens = lens1 > lens2 ? lens1 : lens2;
char ans_tmp[3005] = "";
for (int j = 0; j < lens; j++)
{
if (ans1[j])ans_tmp[j] += ans1[j] - '0';
if (ans2[j])ans_tmp[j] += ans2[j] - '0';
ans_tmp[j] += '0';
if (ans_tmp[j] > '9')ans_tmp[j] -= 10,ans_tmp[j + 1] += 1;
}
if (ans_tmp[lens])
{
ans_tmp[lens++] += '0';
}
for (int j = 0; j < lens; j++)
{
ans[i][lens - j - 1] = ans_tmp[j];
}
}
printf("%s\n", ans[n]);
return 0;
}