「JoyOI1576」楼梯
描述 Description
在你面前有n级台阶。一个合法的走楼梯方案要满足：
第一，你必须先上楼梯，到达某级后连续地下楼梯，直到返回0级。（即开始下楼梯后不能再上楼梯）
第二，每次上下楼梯只能走1级或2级。
第三，由于楼梯只有n级，你不能上到n级以上的位置，也不能下到0级以下的位置。
问共有多少个不同的走楼梯方案。特别地，在0级站着不动也算一种方案。
输入格式 InputFormat
一行两个正整数n和m。
输出格式 OutputFormat
一行一个整数，表示n级台阶有多少种合法的走楼梯方案，答案对m取模。
数据范围和注释 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]
我们可得出递推方程：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
由于我比较懒，就随便写了个递推
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int f[10005]; int main() { n=read();m=read(); f[1]=f[2]=1; for(int i=3;i<=n+2;i++) f[i]=(f[i-1]+f[i-2])%m; printf("%d",(ll)f[n+1]*f[n+2]%m); return 0; } |
Subscribe
计数器 9789121
OI 课件=>
OI 课件=>