hdu 4291(矩阵快速幂+循环节)

A Short problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2487    Accepted Submission(s): 876

Problem Description

　　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 <= 10 ¹⁸), You should solve for 
g(g(g(n))) mod 10 ⁹ + 7
　　where
g(n) = 3g(n - 1) + g(n - 2)
g(1) = 1
g(0) = 0

Input

　　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).

Output

　　For each test case, please print a single line with a integer, the corresponding answer to this case.

Sample Input

0 1 2

Sample Output

0 1 42837

Source

2012 ACM/ICPC Asia Regional Chengdu Online

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Mod1 1000000007
#define Mod2 222222224
#define Mod3 183120
ll Mod;
/*void find()
{
    ll a,b,c,i,k,j;
    a=0,b=1;
    for(i=2;;i++)
    {
        c=(3*b+a)%1000000007;
        if(c==1&&b==0)
           break;
        a=b;
        b=c;
    }
    printf("%lld\n",i-1);
    a=0,b=1;
    for(k=2;;k++)
    {
        c=(3*b+a)%(i-1);
        if(c==1&&b==0)
           break;
        a=b;
        b=c;
    }
    printf("%lld\n",k-1);

    a=0,b=1;
    for(j=2;;j++)
    {
        c=(3*b+a)%(k-1);
        if(c==1&&b==0)
           break;
        a=b;
        b=c;
    }
    printf("%lld\n",j-1);
}
*/
struct Matrix
{
    ll ma[2][2];
    Matrix()
    {
        memset(ma,0,sizeof(ma));
    }

    void init(int a,int b,int c,int d)
    {
        ma[0][0]=a;
        ma[0][1]=b;
        ma[1][0]=c;
        ma[1][1]=d;
    }
    Matrix operator * (const Matrix &m)
    {
        Matrix res;
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                for(int k=0; k<2; k++)
                    res.ma[i][j]=(res.ma[i][j]+m.ma[i][k]*ma[k][j])%Mod;
        return res;
    }
};

Matrix p;

Matrix quick_powm(Matrix m,ll n)
{
    if(n==0)
    {
        p.init(1,0,0,1);
        return p;
    }
    if(n==1)return m;
    Matrix res=quick_powm(m,n/2);
    Matrix ans=res*res;
    if(n%2==1)
        ans=ans*m;
    return ans;
}

ll val;

int main()
{

    while(~scanf("%lld",&val))
    {
        Matrix m,res;
        m.init(3,1,1,0);
        Mod=Mod3;
        res=quick_powm(m,val);
        Mod=Mod2;
        res=quick_powm(m,res.ma[1][0]);
        Mod=Mod1;
        res=quick_powm(m,res.ma[1][0]);
        printf("%lld\n",res.ma[1][0]);
    }
    return 0;
}