数楼梯

高精加+斐波那契数列

https://www.luogu.org/problemnew/show/P1255

输入一个N，

楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

N<=5000

高精度重在灵活多变.....

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<cmath>
 7 #include<set>
 8 #include<vector>
 9 #include<stack>
10 #include<queue>
11 #include<map>
12 using namespace std;
13 #define ll long long
14 #define se second
15 #define fi first
16 const int INF= 0x3f3f3f3f;
17 const int N=4e6+5;
18 
19 int a[5005][5005];
20 
21 int main()
22 {
23     int n;
24     cin>>n;
25     a[1][1]=1;   //第一维表示台阶数，第二维用来输出各位数字 表示 第1阶只有有个位
26     a[2][1]=2;
27     int len=1;
28     for(int i=3;i<=n;i++)
29     {
30         for(int j=1;j<=len;j++)
31             a[i][j]=a[i-1][j]+a[i-2][j];  //各位上的数 先加起来再说
32 
33         for(int j=1;j<=len;j++) //这是对于同一阶i 
34         {
35             if(a[i][j]>=10)
36             {
37                 a[i][j+1] += a[i][j]/10;
38                 a[i][j] %=10;
39             }
40         }
41         if( a[i][len+1] ) len++; //进位
42     }
43     for(int j=len;j>=1;j--)
44         cout<<a[n][j];
45 }