矩阵快速幂

2017 中国大学生程序设计竞赛 女子组
hdu 6030
矩阵快速幂模板
重载结构体运算符实现
主要注意 行列式相乘不能改变顺序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
struct MUL
{
    ll a[4][4];
    MUL operator*(const MUL &k2) const{
        MUL p;
        memset(p.a,0,sizeof p.a);
        for(int i=1;i<=3;i++){
            for(int j=1;j<=3;j++){
                for(int k=1;k<=3;k++){
                    p.a[i][j]=(p.a[i][j]+a[i][k]*k2.a[k][j]%mod)%mod;
                }
            }
        }
        return p;
    }
};


MUL qp(MUL x,ll y)
{
    MUL mu;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(i==j) mu.a[i][j]=1;
            else mu.a[i][j]=0;
        }
    }
    while(y){
        if(y&1) mu=mu*x;
        x=x*x;
        y>>=1;
    }
    return mu;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        if(n==2){
            printf("3\n");
        }
        else if(n==3){
            printf("4\n");
        }
        else if(n==1) printf("1\n");
        else {
            MUL s,w;
            s.a[1][1] = 4 ;s.a[1][2]=3;s.a[1][3]=2;
            for(int i=2;i<=3;i++){
                for(int j=1;j<=3;j++)
                    s.a[i][j]=0;
            }
            w.a[1][1]=1;w.a[1][2]=1;w.a[1][3]=0;
            w.a[2][1]=0;w.a[2][2]=0;w.a[2][3]=1;
            w.a[3][1]=1;w.a[3][2]=0;w.a[3][3]=0;
            MUL ans=qp(w,n-3);
            ans=s*ans;
            printf("%lld\n",ans.a[1][1]%mod);
        }
    }
}