死变态的跳台阶——爬楼梯进阶版本

超、凢脫俗 2022-06-17 13:00 173阅读 0赞

Think:  
1通过递推公式进而得到更加高效规律  
2递推公式代码:

a[1] = 1;
        for(i = 2; i <= 100000; i++){
            a[i] = 1;
            for(j = 1; j < i; j++)///递推公式
                a[i] = (a[i] + a[j])%1000000007;
        }

直接用第一级递推公式，计算时间复杂对会发现达到了5000000000（100000!/2）左右，基本一定超时，因此考虑是否蕴含了更加高效的递推规律公式，进而会发现第二级递推公式a\[n\] = pow(2, n-1)，进而思考代码实现

[sdut题目链接][sdut]  
[sdut爬楼梯题目题目链接][sdut 1]

死变态的跳台阶  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
小银今天准备去爬山，山上的台阶太难爬了，但是小银最近得到了一个新的技能，他每一次可以向上跳一个台阶，也可以两个台阶,也可以三，四，五…….n个台阶。现在已知台阶的数量为n，小银想知道他有多少种方法跳上山顶。

Input  
多组输入，每组输入一个整数n（1 <= n <= 10^5）。

Output  
输出跳上n个台阶总共的跳法，由于结果可能非常的大，结果对1000000007取余。(%1000000007)

Example Input  
1  
2

Example Output  
1  
2

Hint

Author  
绝尘

以下为Time Limit Exceeded代码

#include <stdio.h>
    
    int main()
    {
        int n, i, j;
        int a[100004];
        a[1] = 1;
        for(i = 2; i <= 100000; i++){
            a[i] = 1;
            for(j = 1; j < i; j++)///递推公式
                a[i] = (a[i] + a[j])%1000000007;
        }
        while(scanf("%d", &n) != EOF){
            printf("%d\n", a[n]);
        }
        return 0;
    }

以下为Accepted代码

#include <stdio.h>
    
    int main()
    {
        int n, i, sum;
        while(scanf("%d", &n) != EOF){
            sum = 1;
            for(i = 1; i < n; i++)
                sum = (sum*2)%1000000007;
            printf("%d\n", sum);
        }
        return 0;
    }

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2159/pid/3522
[sdut 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2025/pid/2173