【tyvj1576】楼梯

2014年7月26日1,1470

描述 Description

在你面前有n级台阶。一个合法的走楼梯方案要满足:
第一,你必须先上楼梯,到达某级后连续地下楼梯,直到返回0级。(即开始下楼梯后不能再上楼梯)
第二,每次上下楼梯只能走1级或2级。
第三,由于楼梯只有n级,你不能上到n级以上的位置,也不能下到0级以下的位置。
问共有多少个不同的走楼梯方案。特别地,在0级站着不动也算一种方案。

输入格式 InputFormat

一行两个正整数n和m。

输出格式 OutputFormat

一行一个整数,表示n级台阶有多少种合法的走楼梯方案,答案对m取模。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

对于30%的数据,n<=10000;
对于100%的数据,n<=10^17,m<=2*10^9。

题解
令上楼梯到第i级的总方案数f[i]
我们可得出递推方程:f[i]=f[i-1]+f[i-2]
根据题意,f[0]=1,f[1]=1
这正是斐波拉契数列!
同样的,从第i级下楼梯到底0级的方案数也就等于f[i]
所以,根据乘法原理,上楼梯到第i级再下楼梯回到第0级的方案数就为f[i]^2
于是我们要求的上n级楼梯的所有方案数就等于
f[0]^2+f[1]^2+f[2]^2+…+f[n]^2
根据数学常识,我们知道f[0]^2+f[1]^2+f[2]^2+…+f[n]^2=f[n]*f[n+1]
以上摘自题解T T
由于我比较懒,就随便写了个递推