我们每步可以上 1阶、2阶、3阶 楼梯，那么我们走到第n层楼可以有多少种不同的走法”，众人纷纷思考，不多久已经有了解决方案并回到了宿舍。聪明的你能像他们一样解决这个问题吗？
输入
第一行 T 表示样例组数
每组样例第一行两个整数 n 和 m , n 表示要去的楼层 , m 表示第一层楼到第n层楼之间有m阶台阶（0<n<=100 , 0<m<=10000）
输出
每组样例输出一个整数 表示走到第 n 层楼可以有多少种不同的走法。
样例输入
2
4 10
4 8
样例输出
274
81
提示
<1>m阶台阶可以看成是连续的。
<2>结果对1000000007取模。
------------------------------------------------------
标准答案
------------------------------------------------------
#include <stdio.h>
#define maxn 10200
#define MOD 1000000007
#define LL long long
LL fib[maxn] ;
LL result ;
void init(){
fib[0] = 1 ;
fib[1] = 1 ;
fib[2] = 2 ;
for(int i=3 ; i<=maxn ; i++){
//取模 有时间百度取模 本来想检测 乘积取模
fib[i] = ((fib[i-1]%MOD)+(fib[i-2]%MOD)+(fib[i-3]%MOD))%MOD ;
}
return;
}
int main(){
int t , n , m;
// 预处理出所有答案 , 然后直接调用输出
init() ;
scanf( "%d" , &t);
while(t--){
scanf("%d %d" , &n , &m ) ;
printf( "%lld\n" , fib[m]) ;
}
return 0 ;
}
---------------------------------------------------------
我写的程序有两个 一：#include <stdio.h>
int main()
{
unsigned long long a[10000];
unsigned short i,n,m,q;
scanf("%hd",&q);
while(q--)
{
scanf("%hd%hd",&m,&n);
a[0]=a[1]=1;a[2]=2;
for(i=3;i<=n;i++)
{
a[i]=(a[i-1]%1000000007+a[i-2]%1000000007+a[i-3]%1000000007)%1000000007;
}
printf("%lld\n",a[n]);
}
return 0;
}
二：#include <stdio.h>
unsigned long long a[10000];
void dabiao(unsigned short n)
{
unsigned short i;
a[0]=a[1]=1;a[2]=2;
for(i=3;i<=10000;i++)
{
a[i]=(a[i-1]%1000000007+a[i-2]%1000000007+a[i-3]%1000000007)%1000000007;
}
return;
}
int main()
{
unsigned short i,n,m,q;
scanf("%hd",&q);
while(q--)
{
scanf("%hd%hd",&m,&n);
dabiao(n);
printf("%lld\n",a[n]);
}
return 0;
}
------------------------------------------------------
内个 首先就是那个取模的，为什么不能直接用a[n]%1000000007,我百度不到，如果有这方面资料希望能给我留一下 ：）
然后就是 我想知道，我写的第一个程序 运行耗时是8，而标准答案是0，我差不多改成了第二个程序，也是对的，结果耗时20，希望大牛们可以指点我一下这两个困扰我好久的问题，蟹蟹。
--------------------------
内存 耗时 代码长度
1168 20 C/Edit 513 B
1172 0 C/Edit 671 B
1092 8 C/Edit 390 B
----------------------------------
感谢看完 。 ：）
先给你一份自己刚写的代码：
#include<stdio.h>然后回答你的问题：
1，为什么不能直接取模
可以直接取，取模是符合交换律的，只要保证取模中途不要溢出就行
写三次取模代码很冗余，不好读
2，为什么程序很慢...
因为没必要每次输入都重新算一次
可以直接全部算出来所有的答案，存在数组里，每次问的时候直接输出答案就可以
（也就是把你的第二份代码里面的 dabiao 函数放到循环外面
3，这个题里面的N好像完全没用
4，这个问题有更快的解法...超级快...
叫做矩阵快速幂...感兴趣可以自己去查资料
printf("内存 耗时 语言\n1168 0 C/Edit\n大佬牛掰，写的快而且写的好，十分感谢，还有感谢那个矩阵快速幂的分享，蟹蟹！");