牛客挑战赛32C 斐波那契数列卷积 解题报告

观察题目给出的条件，很容易就可以得出如下式子：

设 表示该数列的第项，则有

而这个式子我们可以通过构造矩阵来快速计算第项

接下来讲一下如何构造矩阵:

我们设一个的矩阵，使得矩阵满足如下条件

这样我们很容易就能构造出这个矩阵

也就是说，我们最终要求的答案就是

只需要写一个矩阵快速幂即可，注意到计算结果和结果矩阵中的第行第列相同，直接输出即可，因为矩阵中存在负数，取模时应先加上

代码：

//Copyright (c) 2019 by xiao_mmQF. All Rights Reserved.
#include<bits/stdc++.h>
#define int __int128
#pragma GCC optimize(3)
#define inl inline
#define reg register
#define db long double
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
inl int read(){ int x=0,f=0; char ch=0; while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar(); return f?-x:x; }
inl void Ot(reg int x) { if(x<0)putchar('-'),x=-x; if(x>=10)Ot(x/10); putchar(x%10+'0'); }
inl void Print(reg int x,char til='\n'){Ot(x);putchar(til);}
inl int Max(reg int x,reg int y){return x>y?x:y;}
inl int Min(reg int x,reg int y){return x<y?x:y;}
inl int Abs(reg int x){return x<0?-x:x;}
const int MAXN=10010;
const int Mod=998244353;
struct Matrix{
    int a[4][4];
    void init(){
        a[0][0]=2;a[0][1]=1;a[0][2]=0;a[0][3]=0;
        a[1][0]=1;a[1][1]=0;a[1][2]=1;a[1][3]=0;
        a[2][0]=-2;a[2][1]=0;a[2][2]=0;a[2][3]=1;
        a[3][0]=-1;a[3][1]=0;a[3][2]=0;a[3][3]=0;
//构造初始矩阵
    }
    Matrix operator*(const Matrix &rhs)const {
        Matrix ret;
        for(reg int i=0;i<4;i++)
        for(reg int j=0;j<4;j++)
        {
            ret.a[i][j]=0;
            for(reg int k=0;k<4;k++)
            ret.a[i][j]+=a[i][k]*rhs.a[k][j],ret.a[i][j]=(ret.a[i][j]+Mod)%Mod;
        }
        return ret;
//定义矩阵乘
    }
}A,B;
int n;
Matrix qpow(Matrix x,int y){
    y -- ;
    Matrix ans = x ;
    for( ; y  ; y >>= 1 , x = x * x)
        if(y & 1) ans = ans * x ;
    return ans;
}//矩阵快速幂
signed main() {
    n=read();
    A.init();
    B=qpow(A,n);
    // for(reg int i=0;i<4;i++,puts(""))
    // for(reg int j=0;j<4;j++)
    // Print(B.a[i][j],' ');
    Print(B.a[0][2]);
    return 0 ;
}