观察题目给出的条件,很容易就可以得出如下式子:
设 表示该数列的第项,则有
而这个式子我们可以通过构造矩阵来快速计算第项
接下来讲一下如何构造矩阵:
我们设一个的矩阵,使得矩阵满足如下条件
这样我们很容易就能构造出这个矩阵
也就是说,我们最终要求的答案就是
只需要写一个矩阵快速幂即可,注意到计算结果和结果矩阵中的第行第列相同,直接输出即可,因为矩阵中存在负数,取模时应先加上
代码:
//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 ; }