Frog


<button class="btn btn&#45;default" id="submit&#95;open&#95;top" type="button"> Submit</button>
&amp;lt;a type=&quot;button&quot; class=&quot;btn btn-warning&quot; href=&quot;/solution/submit.html?problemId=5263&quot;&amp;gt;Submit&amp;lt;/a&amp;gt;
<center> Time Limit: 1 s </center>

Description

There is a little frog called Matt. One day he comes to a river. The river could be considered as an axis. Matt is standing on the left bank now (at position 0 0). He wants to cross the river and reach the right bank (at position N N). But Matt could only jump at most L L units, for example from 0 0 to L L. There are N1 N−1 rocks lying on the river equably (at position 1,2,,N1 1,2,⋯,N−1). The size of the rocks can be ignored, so each rock can be thought as a point on the axis. Matt can jump to a rock from the left bank or other rocks, and he can jump to the right bank from a rock or the left bank.

Now, Matt wants to know how many ways are there to cross the river. Of course, Matt could only jump forward.

 

Input

There are no more than 100 100 cases. Each case contains two integers N N (2N100000) (2≤N≤100000) and L L (1LN) (1≤L≤N), denoting the position of the right bank and the distance Matt could jump most.

 

Output

For each test case, print the number of way to cross the river module 10 9 +7 109+7.

 

Sample Input

3 1
4 3

 

Sample Output

1
7

 


Author: Matt


思路:

典型的爬楼梯问题。O(N)复杂度可以解决。

/* 爬楼梯问题:每次可以跨上1…M个台阶,一共有N个台阶,问从最底下爬到最高处有几种爬法 */  
#include <stdio.h>  
#define MAX 100  
/* 共n个台阶,每次最多m个台阶,f[i]保存爬n个台阶的爬法总数,返回f[n] 
 * 优化版O(n) 
 */  
long long PaLouTi(const int n, const int m, long long * const f)  
{   
    int i;  
    f[0] = f[1] = 1;  
    for (i = 2; i <= m; ++ i)  
        f[i] = f[i - 1] * 2;  
    for (i = m + 1; i <= n; ++ i)  
        f[i] = f[i - 1] * 2 - f[i - m - 1];  
    return f[n];  
}  
/* 共n个台阶,每次最多m个台阶,f[i]保存爬n个台阶的爬法总数,返回f[n] 
 * 原版O(n^2) 
 */  
long long PaLouTi2(const int n, const int m, long long * const f)  
{  
    int i, j, max1;  
    f[0] = 1;  
    for (i = 1; i <= n; ++ i)  
        for (f[i] = 0, max1 = i - m > 0 ? i - m : 0, j = i - 1; j >= max1; -- j)  
            f[i] += f[j];  
    return f[n];  
}  
int main()  
{  
    long long f[MAX];  
    int M, N;  
    while (printf("M, N : "), scanf("%d %d", &M, &N) == 2)  
    {  
        printf("%I64d %I64d/n", PaLouTi(N, M, f), PaLouTi2(N, M, f));  
    }  
    return 0;  
}  
f[n] = f[n <= m ? 1 : n - m] + ... + f[n - 1]


这里还要注意的一点是,在模1000000007的时候,不能只在最后模,在运算中也要时刻模,并且,要注意到-5%10=-5,也就是说负数的模还是负数,那么就要+1000000007再模。切记。



代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
 
long long f[100000+5];
 
long long PaLouTi(int n,int m)  
{   
    int i;  
    f[0]=f[1]=1;  
    for(i=2;i<=m;++i)  
        f[i]=(f[i-1]*2)%1000000007;  
    for(i=m+1;i<=n;++i)  
        f[i]=((f[i-1]*2)-(f[i-m-1])+1000000007)%1000000007;  
    return f[n]%1000000007;  
}  
 
int main()  
{  
    int n,l;  
    while(~scanf("%d%d",&n,&l))  
    {  
        printf("%d\n", PaLouTi(n,l)%1000000007);  
    }  
    return 0;  
}