IPUxinao @ 2024-09-03 11:43:54
#include<bits/stdc++.h>
using namespace std;
struct Bigint{
int len,a[1000];//len记录位数,a记录每个数位
Bigint(int x=0){
memset(a,0,sizeof(a));
for(len=1;x;len++){
a[len]=x%10,x/=10;
}
len--;
}
int &operator[](int i){
return a[i];
}
void flatten(int L){//一口气处理1到L范围内的进位并重置长度,需要保证L不小于有效长度
len=L;
for(int i=1;i<=len;i++){
a[i+1]+=a[i]/10,a[i]%=10;
}
for(;!a[len];){//重置长度成为有效长度
len--;
}
}
void print(){//输出
for(int i=max(len,1);i>=1;i--){
printf("%d",a[i]);
}
}
};
Bigint operator+(Bigint a,Bigint b){
Bigint c;
int len=max(a.len,b.len);
for(int i=1;i<=len;i++){
c[i]+=a[i]+b[i];
}
c.flatten(len+1);
return c;
}
int main()
{
int N;
cin>>N;
Bigint f[5010];
f[1]=Bigint(1);
f[2]=Bigint(2);
for(int i=3;i<=N;i++){
f[i]=f[i-1]+f[i-2];
}
f[N].print();
return 0;
}
by Focalors_HuTao @ 2024-09-03 11:51:54
使用dp,要我的代码不
by cxf2012 @ 2024-09-03 12:00:17
@IPUxinao 我记得小升初有这种题
by IPUxinao @ 2024-09-03 12:40:47
@Focalors_HuTao 要的,谢谢大佬
by IPUxinao @ 2024-09-03 12:41:46
因为这就是按照《深基》上的方法写的,所以最后一个点过不去就很蒙。
by abc13806599977 @ 2024-09-07 13:12:23
int len,a[1000];//len记录位数,a记录每个数位 位数有1050位