首页 > 代码库 > codevs 1606 台阶

codevs 1606 台阶

时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 黄金 Gold
题目描述 Description

话说某牛家门外有一台阶,这台阶可能会很高(总层数<=1000000)。

这牛刚开始是在台阶外面,可以认为是在0层。每次可以跨一步或两步,但有时某层台阶上会被人泼上脏水,这层就不能走了~~

(这个可怜的货)

所以请你编程,输出这牛到达家的路径总数(不能经过被泼脏水的台阶)。

输入描述 Input Description

共一行,两个数。

分别表示台阶的总层数和不能踩的台阶。

输出描述 Output Description

走法总数。

样例输入 Sample Input

5 3

样例输出 Sample Output

2

{说明:

样例的路径为:

0-1-2-4-5

0-2-4-5}

数据范围及提示 Data Size & Hint

由于数据可能太大,请输出结果 mod 123321的值。

不要想太多哦!

 

递推 斐波那契数列 

屠龙宝刀点击就送

#include <cstdio>int n,m,f[1000000];int main(){    scanf("%d%d",&n,&m);    f[0]=1;    if(m!=1) f[1]=1;    for(int i=2;i<=n;++i) if(i!=m) f[i]=(f[i-1]+f[i-2])%123321;    printf("%d",f[n]);}

 

codevs 1606 台阶