首页 > ACM题库 > HDU-杭电 > HDU 4291-A Short problem-快速幂-[解题报告]HOJ
2015
05-23

HDU 4291-A Short problem-快速幂-[解题报告]HOJ

A Short problem

问题描述 :

  According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
  Hence they prefer problems short, too. Here is a short one:
  Given n (1 <= n <= 1018), You should solve for
g(g(g(n))) mod 109 + 7

  where
g(n) = 3g(n – 1) + g(n – 2)

g(1) = 1

g(0) = 0

输入:

  There are several test cases. For each test case there is an integer n in a single line.
  Please process until EOF (End Of File).

输出:

  There are several test cases. For each test case there is an integer n in a single line.
  Please process until EOF (End Of File).

样例输入:

0
1
2

样例输出:

0
1
42837

补充一个知识:摸运算肯定会出现的循环节的。那么循环嵌套,对内层求MOD,层层向外跳出。

现暴力求出循环节,然后用矩阵的快速幂。

构找矩阵的方法:

一般的对于线性递推方程fn=a1fn-1+a2fn-2+……+aifn-i

线性递推方程即形如 fn=a1fn-1+a2fn-2+……+aifn-i的方程

以斐波那契数列为例 an=an-1+an-2

我们的目的是通过矩阵乘法,求得斐波那契数列的第n项,为了得到这个结果,我们还需要由[an-2 an-1]推得[an-1 an]

我们设[an-2 an-1]为矩阵A,因为A1×2B2×2=C1×2,所以C与A是同规模的矩阵

[an-2 an-1] = [an-1 an]

一般的对于线性递推方程fn=a1fn-1+a2fn-2+……+aifn-i

可以建立B=

设A=[f1 f2 f3 …… fi],则由ABB……B(k个B)即可得到fi+k

 

可以建立矩阵。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<set>
#include<cstdio>
#include<iostream>
#define N 2
#define LL long long
using namespace std;
const LL MOD1 = 1000000007LL;
//222222224
const LL MOD2 = 222222224LL;
//183120
const LL MOD3 = 183120LL;
struct matrix
{
    long long  m[N][N];
};
matrix p= {0,1,//左乘矩阵
           1,0,
          };
matrix I= {0,1,//要幂乘的矩阵
           1,3,
          };
matrix unin={1,0,//单位矩阵
             0,1,
            };
matrix matrixmul(matrix a,matrix b,long long  mod)//矩阵a乘矩阵b
{
    matrix c;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
        {
            c.m[i][j]=0;
            for(int k=0; k<N; k++)
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
            c.m[i][j]%=mod;
        }
    return c;
}
matrix qiuckpow(long long n,long long  mod)
{
    matrix m=I,b=unin;//求矩阵I的n阶矩阵
    while(n>=1)
    {
        if(n&1)
            b=matrixmul(b,m,mod);
        n=n>>1;
        m=matrixmul(m,m,mod);
    }
    return matrixmul(p,b,mod);
}
long long  n;
int main()
{
    while(scanf("%I64d",&n)!=EOF)
    {
        matrix ans;
        ans=qiuckpow(n,MOD3);
        ans=qiuckpow(ans.m[0][0],MOD2);
        ans=qiuckpow(ans.m[0][0],MOD1);
        cout<<ans.m[0][0]<<endl;
//        for(int i=0;i<2;i++)
//        {
//             for(int j=0;j<2;j++)
//                cout<<ans.m[i][j]<<' ';
//             cout<<endl;
//        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/weiguang_123/article/details/7994432