矩阵快速幂（模板）（求通项公式的第几项通常用其求解）

题目：有规律的斐波那契
求通项公式的第几项通常用矩阵快速幂求解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=998244353;
struct L{
    ll a[3][3];
    void init(int f=0){     //默认参数为0
        memset(a,0,sizeof a);
        if(f==1){   //将其初始化为单位矩阵
            this->a[0][0]=this->a[1][1]=this->a[2][2]=1;
        }
        if(f==2){   //将其初始化为构造矩阵
            this->a[0][0]=this->a[0][1]=
            this->a[0][2]=this->a[1][0]=
            this->a[2][1]=1;
        }
        if(f==3){   //将其初始化为含斐波那契矩阵  //即通项公式最初的样子
            this->a[0][0]=2;
            this->a[1][0]=this->a[2][0]=1;
        }
    }
    L operator*(L const &b){
        L res;
        res.init();
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                for(int k=0;k<3;++k){
                    res.a[i][j]=(res.a[i][j]+this->a[i][k]*b.a[k][j]%mod)%mod;  //a[i][k]*b[k][j] 表示第i行第k个乘第j列第k个 //多维矩阵相乘也是这一句代码    //这里当心出错 
                }
            }
        }
        return res;
    }
};
L ksm(L a,ll b){     
    L res;res.init(1);
    while(b){
        if(b&1){  //快速幂是按位的多少运算（将b看成二进制），所以最多执行64次
            res=res*a;
        }
        a=a*a;
        b >>= 1;
    }
    return res; 
}
ll t,x;
int main(){
    cin >> t;
    L m1,m2;
    while(t--){
        cin >> x;
        m2.init(3);
        if(x<3) cout << m2.a[2-x][0] << "\n";
        else {
            m1.init(2); 
            cout << (ksm(m1,x-2)*m2).a[0][0] << "\n";
        } 
    }
    return 0;
}