学步园

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

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

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

0
1
2

0
1
42837


小结：花了好长时间来看这题，最后还是搞懂了，1A，呵呵。
这题有几个方面值得关注：
1.矩阵乘法与数列结合，给你数列的递推公式，让你求第n项的值。用矩阵的幂来完美解决了。
2.取模都会有循环节，有点不懂的是，求循环节的时候总是只要判断2个元素就可以了。这里附上求循环节的代码.
#include<stdio.h>
const long long MOD=222222224;//第一次是MOD=1000000007 找出循环节是222222224
//第二次是MOD=222222224，找出循环节183120
int main()
{
    long long a,b;
    a=1;
    b=3;
    for(int i=1;;i++)
    {
        if(a==0&&b==1)
        {
            printf("%d\n",i);
            break;
        }
        long long c=3*b+a;
        c%=MOD;
        a=b;
        b=c;
    }
    return 0;
}
本题代码：

#include<iostream>
#include<cstdio>
#define ll __int64
#define MOD3 1000000007
#define MOD2 222222224
#define MOD1 183120
using namespace std;
struct Mat
{
    int n,m;
    ll a[5][5];
};
Mat MUL(Mat x,Mat y,ll mod)
{
    Mat tp;
    int n=x.n,m=y.m,l=x.m;
    tp.n=n,tp.m=m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            tp.a[i][j]=0;
            for(int k=0;k<l;k++)
            {
                tp.a[i][j]=(tp.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
            }
        }
    }
    return tp;
}
Mat POW(Mat x,ll n,ll mod)
{
    Mat tp;
    tp.m=tp.n=2,tp.a[0][0]=1,tp.a[0][1]=0,tp.a[1][0]=0,tp.a[1][1]=1;
    while(n)
    {
        if(n&1)
        {
            tp=MUL(tp,x,mod);
        }
        n/=2;
        x=MUL(x,x,mod);
    }
    return tp;
}

int main()
{
    ll n;
    Mat A,g0;
    A.m=A.n=2,A.a[0][0]=3,A.a[0][1]=1,A.a[1][0]=1,A.a[1][1]=0;
    g0.n=2,g0.m=1,g0.a[0][0]=1,g0.a[1][0]=0;
    while(scanf("%I64d",&n)!=EOF)
    {
        Mat tmp1=POW(A,n,MOD1);
        tmp1=MUL(tmp1,g0,MOD1);
        ll tt=tmp1.a[1][0];

        Mat tmp2=POW(A,tt,MOD2);
        tmp2=MUL(tmp2,g0,MOD2);
        tt=tmp2.a[1][0];

        Mat tmp3=POW(A,tt,MOD3);
        tmp3=MUL(tmp3,g0,MOD3);
        tt=tmp3.a[1][0];
        printf("%I64d\n",tt);
    }
    return 0;
}