2020-08-10 数楼梯

https://www.luogu.com.cn/problem/P1255

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 5010//高精的位数

long long qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}


int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

//int peace(int floor){
//    if (floor == 2) {
//        return 2;
//    }
//    if(floor == 1){
//        return 1;
//    }
//    if (f[floor]!=0) {
//        return f[floor];
//    }
//    f[floor] = peace(floor-1)+peace(floor-2);
//    return f[floor];
//}

int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数
void hp(int k)//高精度加法，k来存阶数
{
    int i;
    for(i=1;i<=len;i++)
     f[k][i]=f[k-1][i]+f[k-2][i];//套用公式
    for(i=1;i<=len;i++)             //进位
     if(f[k][i]>=10)
     {
         f[k][i+1]+=f[k][i]/10;
         f[k][i]=f[k][i]%10;
         if(f[k][len+1])len++;
    }
}

int main()
{
    int i;
    scanf("%d",&n);
    f[1][1]=1; f[2][1]=2;         //初始化
    for(i=3;i<=n;i++)              //从3开始避免越界
     hp(i);
    for(i=len;i>=1;i--)             //逆序输出
     printf("%d",f[n][i]);
    return 0;
}
/*
4
============
5
*/