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);
}
}
}