杭電 oj Array Challenge(矩陣快速幂+找規律）

題目連結：​​這裡寫連結内容​​

先求出式子的前幾項

然後這個式子和h的式子是非常像的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
#include<cctype>
using namespace std;
#define ll long long
#define edl putchar('\n')
#define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define FORLL(i,a,b) for(ll i=a;i<=b;i++)
#define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
#define mst(a) memset(a,0,ssizeof(a))
#define mstn(a,n) memset(a,n,ssizeof(a))
#define zero(x)(((x)>0?(x):-(x))<eps)
const int ssize=3;
const int mod=1000000007;
struct Matrix {
    ll a[ssize][ssize];
    Matrix() {
        memset(a,0,sizeof(a));
    }
    void init() {
        for(int i=0; i<ssize; i++)
            for(int j=0; j<ssize; j++)
                a[i][j]=(i==j);
    }
    Matrix operator + (const Matrix &B)const {
        Matrix C;
        for(int i=0; i<ssize; i++)
            for(int j=0; j<ssize; j++)
                C.a[i][j]=(a[i][j]+B.a[i][j])%mod;
        return C;
    }
    Matrix operator * (const Matrix &B)const {
        Matrix C;
        for(int i=0; i<ssize; i++)
            for(int k=0; k<ssize; k++)
                for(int j=0; j<ssize; j++)
                    C.a[i][j]=(C.a[i][j]%mod+1LL*a[i][k]*B.a[k][j]%mod+mod)%mod;
        return C;
    }
    Matrix operator ^ (const ll &t)const {
        Matrix A=(*this),res;
        res.init();
        ll p=t;
        while(p) {
            if(p&1)res=res*A;
            A=A*A;
            p>>=1;
        }
        return res;
    }
};

int main() {

    int t;
    scanf("%d",&t);
    Matrix a,b;
    Matrix ans;
    a.a[0][0]=4,a.a[0][1]=17,a.a[0][2]=-12;
    a.a[1][0]=1,a.a[1][1]=0,a.a[1][2]=0;
    a.a[2][0]=0,a.a[2][1]=1,a.a[2][2]=0;
    b.a[0][0]=1255,b.a[1][0]=197,b.a[2][0]=31;
    while(t--){
        ll n;
        scanf("%lld",&n);
        if (n == 2)
        {
            printf("31\n");
            continue;
        }
        else if (n == 3)
        {
            printf("197\n");
            continue;
        }
        else if (n == 4)
        {
            printf("1255\n");
            continue;
        }
        else{
            ans=a^(n-4);
            ll res=(ans.a[0][0]*1255%mod+ans.a[0][1]*197%mod+ans.a[0][2]*31%mod+mod)%mod;
            printf("%lld\n",res);
        }
    }   
}