Codeforces Round #118 (Div. 1) A. Plant

A. Plant

题目链接：http://codeforces.com/problemset/problem/185/A

题意：一个植物会长，一开始是一个正三角形，每过一年，一个向上的正三角形会变成三个向上的正三角形和一个向下的正三角形，一个向下的三角形可以变成三个向下的三角形和一个向上的三角形，问n年后有多少个向上的正三角形，和向下的正三角形，这是一个矩阵快速幂的裸题，很容易可以推出递推式，然后利用矩阵快速幂求就好了。

设向上三角形的数量为an，向下三角形数量为bn，则an=3*an-1+bn，bn=3*bn+an，根据这个递推式，我们可以构造矩阵求解。

3,1  * an-1  = an

1,3    bn-1 = bn

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define n 2
#define MOD 1000000007
using namespace std;
typedef long long ll;
struct Matrix{
    ll mat[2][2];
    Matrix operator * (const Matrix & m) const{
        Matrix tmp;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                tmp.mat[i][j]=0;
                for(int k=0;k<n;k++){
                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;
                    tmp.mat[i][j]%=MOD;
                }
            }
        return tmp;
    }
};
Matrix POW(Matrix m,ll k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=0;i<n;i++) ans.mat[i][i]=1;
    while(k){
        if(k&1) ans=ans*m;
        k/=2;
        m=m*m;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    ll T;
    cin>>T;
    Matrix m;
    m.mat[0][0]=m.mat[1][1]=3;
    m.mat[0][1]=m.mat[1][0]=1;
    Matrix ans;
    ans=POW(m,T);
    cout<<ans.mat[0][0]%MOD<<endl;
    return 0;
}