站点图标 陌路寒暄

H胖胖的健身计划

code

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

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
#define mod 100007
 
typedef struct matrix
{
    long long a1,a2,a3,a4;
    matrix operator * (const matrix& w)
    {
        matrix res;
        res.a1=(a1*w.a1%mod+a2*w.a3%mod)%mod;
        res.a2=(a1*w.a2%mod+a2*w.a4%mod)%mod;
        res.a3=(a3*w.a1%mod+a4*w.a3%mod)%mod;
        res.a4=(a3*w.a2%mod+a4*w.a4%mod)%mod;
        return res;
    }
};
 
long long qpow(long long n)
{
    matrix base;
    matrix ans;
    ans.a1=ans.a2=ans.a4=1;
    ans.a3=0;
    base.a1=base.a2=base.a3=1;
    base.a4=0;
    while(n){
        if(n&1)ans=base*ans;
        base=base*base;
        n>>=1;
    }
    return ans.a1;
}
 
int main()
{
    //freopen("in8.txt","r",stdin);
    //freopen("out8.txt","w",stdout);
    long long n=0;
    long long ans=0;
    scanf("%lld",&n);
    ans=qpow(n);
    printf("%lld\n",ans);
}

参考答案（时间最优[2]）：

#include <iostream>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const long long mod = 100007;
struct node {
    long long mp[2][2];
    void init(long long a, long long b, long long c, long long d) {
        mp[0][0] = a;
        mp[0][1] = b;
        mp[1][0] = c;
        mp[1][1] = d;
    }
    void mult(node x, node y) //两矩阵乘法
    {
        memset(mp, 0, sizeof(mp));
        for (long long i = 0; i < 2; i++)
            for (long long j = 0; j < 2; j++)
                for (long long k = 0; k < 2; k++)
                    mp[i][j] = (mp[i][j] + x.mp[i][k] * y.mp[k][j]) % mod;
    };
} init;

struct node expo(struct node x, long long k) //进行k次幂运算
{
    struct node tmp;
    tmp.init(1, 0, 0, 1); //单位矩阵
    while (k)             //快速幂部分
    {
        if (k & 1)
            tmp.mult(tmp, x);
        x.mult(x, x);
        k >>= 1;
    }
    return tmp;
}
int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // LOCAL_IM0QIANQIAN

    long long k;
    scanf("%lld", &k);
    init.init(1, 1, 1, 0); //初始化矩阵(1 1 1 0)
    printf("%lld\n", expo(init, k+1).mp[0][1] % mod);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。

退出移动版