题面
题目就是一个找规律地题，主要wa了好多次原因是没有想到用快速幂。
AC代码
#include<algorithm>
#include<cassert>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<list>
#include<stack>
using namespace std;
long long mod_mul(long long a,long long b,long long p) {long long r=0;long long t=a; while(b) {if(b&1) r=(r+t)%p;t=(t<<1)%p;b>>=1;}return r;
}
long long mod_pro(long long a,long long b,long long p) {long long r=1;long long t=a; while(b) {if(b&1) r=mod_mul(r,t,p)%p;t=mod_mul(t,t,p)%p;b>>=1;}return r;
}
int main(){long long n;long long mod=1000000007;while(~scanf("%I64d",&n)){if(n==1)cout<<1<<endl;else if(n==2)cout<<4<<endl;else{printf("%d\n",(4*mod_pro(3,n-2,mod))%mod);}}return 0;
}关于快速幂
ll ksm(ll a,ll b)
{ll res=1;while(b){if(b&1) res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}关于矩阵快速幂
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod = 10000;
const int maxn = 35;
int N;
struct Matrix {int mat[maxn][maxn];int x, y;Matrix() {memset(mat, 0, sizeof(mat));for (int i = 1; i <= maxn - 5; i++) mat[i][i] = 1;}
};
inline void mat_mul(Matrix a, Matrix b, Matrix &c) {memset(c.mat, 0, sizeof(c.mat));c.x = a.x; c.y = b.y;for (int i = 1; i <= c.x; i++) {for (int j = 1; j <= c.y; j++) {for (int k = 1; k <= a.y; k++) {c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod;c.mat[i][j] %= mod;}}}return ;
}
inline void mat_pow(Matrix &a, int z) {Matrix ans, base = a;ans.x = a.x; ans.y = a.y;while (z) {if (z & 1 == 1) mat_mul(ans, base, ans);mat_mul(base, base, base);z >>= 1;}a = ans;
}
int main() {while (cin >> N) {switch (N) {case -1: return 0;case 0: cout << "0" << endl; continue;case 1: cout << "1" << endl; continue;case 2: cout << "1" << endl; continue;}Matrix A, B;A.x = 2; A.y = 2;A.mat[1][1] = 1; A.mat[1][2] = 1;A.mat[2][1] = 1; A.mat[2][2] = 0;B.x = 2; B.y = 1;B.mat[1][1] = 1; B.mat[2][1] = 1;mat_pow(A, N - 1);mat_mul(A, B, B);cout << B.mat[1][1] << endl;}return 0;
}