题目描述
L老师布置了一道思考题,一个人一次可以上一个台阶,也可以上两个台阶,问上到n级台阶有多少种走法?H胖胖非常聪明,拿出胖胖的小手掐指算起来。登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种方法……所以,1,2,3,5,8,13,……。
H胖胖为了保持身体苗条,给自己制定了一个锻炼计划,决定用刚才计算的数列确定每天自己锻炼的步数,就是说第1天走1步,第2天走2步,第3天走5步,第4天走8步,第5天走13步,……。
H胖胖的同学LYQ正好在学习矩阵相乘,帮他想到了一个快递计算的方法如下公式所示。
H胖胖拿出手机查阅了快速幂的百度百科,看到如下信息:
快速幂
顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。
原理
以下以求a的b次方来介绍:
把b转换成二进制数。
该二进制数第i位的权为
例如
11的二进制是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
因此,我们将a¹¹转化为算
但是H胖胖的手机太不给力,后面的代码实在看不清了,请正在做题的你帮帮他吧。
输入
一个整数n(0<n<10^12)
输出
H胖胖走的步数%100007的结果
样例输入
6
样例输出
13
参考代码
#include<stdio.h>
const int mod=100007;
int main()
{
long long a[2][2]={{1,0},{0,1}},b[2][2]={{1,1},{1,0}},c[2][2]={{0,0},{0,0}},x,i,j,k;
scanf("%lld",&x);
while(x)
{
if(x&1)
{
for (i=0;i<2;i++)
for (j=0;j<2;j++)
c[i][j]=0;
for (i=0;i<2;i++)
for (j=0;j<2;j++)
for (k=0;k<2;k++)
{
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
for (i=0;i<2;i++)
for (j=0;j<2;j++)
a[i][j]=c[i][j];
}
for (i=0;i<2;i++)
for (j=0;j<2;j++)
c[i][j]=0;
for (i=0;i<2;i++)
for (j=0;j<2;j++)
for (k=0;k<2;k++)
{
c[i][j]+=b[i][k]*b[k][j];
c[i][j]%=mod;
}
for (i=0;i<2;i++)
for (j=0;j<2;j++)
b[i][j]=c[i][j];
x>>=1;
}
printf("%lld",a[0][0]);
}
解析
暂无