洛谷 P1255. 高精度斐波那契楼梯
原题链接
简单
作者:
倒吊袋鼠
,
2022-09-27 23:37:16
,
所有人可见
,
阅读 191
#include <iostream>
#include <vector>
using namespace std;
vector<int> res[5010];
vector<int> add(vector<int> &A,vector<int> &B)
{
if(A.size() < B.size()) return add(B,A);
vector<int> C;
int t = 0;
for(int i = 0; i < A.size() ;i++)
{
t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);
return C;
}
int main()
{
res[0].push_back(0);
res[1].push_back(1);
res[2].push_back(2);
int n;
cin >> n;
for(int i = 3;i <= 5001; i++)
{
auto C = add(res[i-1],res[i-2]);
//res[i] = C;
res[i].assign(C.begin(),C.end());//赋值
}
for(int i = res[n].size()-1;i >= 0; i--) cout << res[n][i];
}