H胖胖的健身计划
时间: 1ms 内存:128M
描述:
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
提示:
参考答案:
文章评论