这个模板适用于解决矩阵快速幂的问题：

题目背景：

已知数列ai，满足 ai = x* (ai-1) + y* (ai-2) ,已知x,y,a0,a1,

让你求这个数列的第k项

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
struct node{
    ll m[2][2];
    node(){
        memset(m,0,sizeof(m));
    }
    friend node operator *(node a,node b){
          node ans;
          for(int i=0;i<2;i++)
              for(int j=0;j<2;j++)
                  for(int k=0;k<2;k++)
                      ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%mod;
          return ans;
    }
    friend node pow(node a,ll k){
        node ans;
        ans.m[0][0] = ans.m[1][1] = 1,ans.m[0][1] = ans.m[1][0] = 0;
        while(k){
            if(k&1)
                ans = ans*a;
            a = a*a;
            k >>= 1;
        }
        return ans;
    }
};
node a,ans;
ll k;
int main()
{
    ll x,y,a0,a1;
    cin>>k>>x>>y>>a0>>a1;
    k -= 1;
    ans.m[0][0] = ans.m[1][1] = 1,ans.m[1][0] = ans.m[0][1] = 0;
    a.m[0][0] = x ,a.m[0][1] = y ,a.m[1][0] = 1 ,a.m[1][1] = 0;
    ans = pow(a,k);
    cout<<(a1*ans.m[0][0] + a0*ans.m[0][1])%mod<<endl;
    return 0;
}

如果k大于等于(10^100),，即求ak，那就需要用到十进制快速幂 + 矩阵快速幂

模板：已知数列ai，满足 ai = x* (ai-1) + y* (ai-2) ,已知x,y,a0,a1,

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
char s[100005];
struct node{
    ll m[2][2];
    node(){
        memset(m,0,sizeof(m));
    }
    friend node operator *(node a,node b){
          node ans;
          for(int i=0;i<2;i++)
              for(int j=0;j<2;j++)
                  for(int k=0;k<2;k++)
                      ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%mod;
          return ans;
    }
    friend node pow(node a,ll k)
    {
        node ans;
        ans.m[0][0] = ans.m[1][1] = 1,ans.m[0][1] = ans.m[1][0] = 0;
        while(k){
            if(k&1)
                ans = ans*a;
            a = a*a;
            k >>= 1;
        }
        return ans;
    }
};
node a,ans;
int main()
{
    ll x,y,a0,a1;
    cin>>x>>y>>a0>>a1;
    scanf("%s",s+1);
    int len = strlen(s+1);
    ans.m[0][0] = ans.m[1][1] = 1,ans.m[1][0] = ans.m[0][1] = 0;
    a.m[0][0] = x ,a.m[0][1] = y ,a.m[1][0] = 1 ,a.m[1][1] = 0;
    for(int i=len;i>=1;i--){
        ans = ans*pow(a,s[i] - '0');
        a = pow(a,10);
    }
    cout<<(a1*ans.m[1][0] + a0*ans.m[1][1])%mod<<endl;
    return 0;
}