牛客挑战赛32-C斐波那契数列卷积

一开始看题目，觉得是卷积，但搞了半天搞不出来。听别人说能推公式，但一直推不出来。
看了题解才知道了递推式：

知道这个，直接就是一个矩阵快速幂的模板题了（其实矩阵快速幂难就难在递推式的推导）。
但这样只能过90%的数据，还要用快读优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n;
struct matrix
{
    ll mat[6][6];
    void clc()
    {
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                mat[i][j]=0;
    }
    void eye()
    {
        for(int i=1;i<=4;i++)
            mat[i][i]=1;
    }
    matrix operator *(const matrix &b)const
    {
        matrix res;
        res.clc();
        for(int i=1;i<=4;i++)
        {
            for(int k=1;k<=4;k++)
            {
                if(mat[i][k])
                for(int j=1;j<=4;j++)
                    res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]%mod+mod)%mod;
            }
        }
        return res;
    }
};
ll read( )
{
    char ch=getchar();
    int f=1;
    ll res=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
void init(matrix &a)
{
    a.clc();
    for(int i=1;i<=4;i++)
    {
        if(i==1)
        {
            a.mat[i][1]=2;
            a.mat[i][2]=1;
            a.mat[i][3]=-2;
            a.mat[i][4]=-1;
        }
        else
            a.mat[i][i-1]=1;
    }
}
void init2(matrix &b)
{
    b.clc();
    b.mat[1][1]=2;
    b.mat[2][1]=1;
}
matrix MPOW(matrix a,ll b)
{
    matrix res;
    res.clc();
    res.eye();
    while(b)
    {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int main()
{
    matrix A;
    init(A);
    matrix B;
    init2(B);
    n=read();
    //cout<<n<<endl;
    if(n>=3)
    {
        matrix ans=MPOW(A,n-3)*B;
        printf("%lld\n",(ans.mat[1][1]%mod+mod)%mod);
    }
    else
    {
        if(n==1)
            puts("0");
        if(n==2)
            puts("1");
        if(n==3)
            puts("2");
    }

    return 0;
}