A Short problem

/* * Author: lyucheng * Created Time:  2017年05月20日 星期六 16时40分42秒 * File Name: HDU-4291-A_Short_problem.cpp */ /* * 题意:让你求g(g(g(n)))mod 1e9+7,其中g(n)=3*g(n-1)+g(n-2) * * * 思路:g(n)可以通过矩阵快速幂求出来,但是干后分别求出各自的循环节,能得到第一个循环节是222222224, *      第二个循环节是183120 * */#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <stack>#include <queue>#include <set>#include <time.h>#define LL long long#define maxn 3  using namespace std;LL n;LL mod;/********************************矩阵快速幂**********************************/class Matrix {    public:        LL a[maxn][maxn];        void init() {            memset(a,0,sizeof(a));        }                Matrix operator +(Matrix b) {            Matrix c;            for (int i = 0; i < 2; i++)                for (int j = 0; j < 2; j++)                    c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;            return c;        }        Matrix operator +(LL x) {            Matrix c = *this;            for (int i = 0; i < 2; i++)                c.a[i][i] += x;            return c;        }        Matrix operator *(Matrix b)        {            Matrix p;             p.init();            for (int i = 0; i < 2; i++)                for (int j = 0; j < 2; j++)                for (int k = 0; k < 2; k++)                    p.a[i][j] = (p.a[i][j] + (a[i][k]*b.a[k][j])%mod) % mod;            return p;        }        Matrix power(LL t) {            Matrix ans,p = *this;            ans.init();            ans.a[0][0]=1;            ans.a[1][1]=1;            while (t) {                if (t & 1)                    ans=ans*p;                p = p*p;                t >>= 1;            }            return ans;        }}unit,init;/********************************矩阵快速幂**********************************/int main(int argc, char* argv[]){    // freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout;    while(scanf("%lld",&n)!=EOF){        if(n<2){            printf("%lld\n",n);            continue;        }        //首先求最里面的g(n)        mod=183120;        unit.init();        unit.a[0][0]=1,unit.a[0][1]=0,unit.a[1][0]=0,unit.a[1][1]=0;        init.a[0][0]=3,init.a[0][1]=1,init.a[1][0]=1,init.a[1][1]=0;        init=init.power(n-1);        unit=unit*init;        n=unit.a[0][0];                if(n>=2){//很重要,要不然当n<2的时候矩阵乘法就会死循环            mod=222222224;            unit.init();            unit.a[0][0]=1,unit.a[0][1]=0,unit.a[1][0]=0,unit.a[1][1]=0;            init.a[0][0]=3,init.a[0][1]=1,init.a[1][0]=1,init.a[1][1]=0;            init=init.power(n-1);            unit=unit*init;            n=unit.a[0][0];        }                if(n>=2){//很重要,要不然当n<2的时候矩阵乘法就会死循环            mod=1000000007;            unit.init();            unit.a[0][0]=1,unit.a[0][1]=0,unit.a[1][0]=0,unit.a[1][1]=0;            init.a[0][0]=3,init.a[0][1]=1,init.a[1][0]=1,init.a[1][1]=0;            init=init.power(n-1);            unit=unit*init;            n=unit.a[0][0];        }        printf("%lld\n",n);    }    return 0;}