https://ac.nowcoder.com/acm/contest/1087/C
列出a[i],a[i-1],a[i-2]，发现a[i]=a[i-1]+a[i-2]+f[i-1];
然后构造矩阵跑矩阵快速幂即可
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #define ull unsigned long long 4 #include <bits/stdc++.h> 5 #define iter ::iterator 6 #define pa pair<int,ll> 7 #define pp pair<int,pa> 8 using namespace std; 9 #define ll long long 10 #define mk make_pair 11 #define pb push_back 12 #define se second 13 #define fi first 14 #define ls o<<1 15 #define rs o<<1|1 16 const int N=1e5+5; 17 ll mod=998244353; 18 struct node{ 19 ll a[10][10]; 20 node(){} 21 node operator *(const node &t)const{ 22 node res; 23 for(int i=1;i<=4;i++){ 24 for(int j=1;j<=4;j++){ 25 res.a[i][j]=0; 26 } 27 } 28 for(int i=1;i<=4;i++){ 29 for(int j=1;j<=4;j++){ 30 31 for(int k=1;k<=4;k++){ 32 res.a[i][j]+=(a[i][k]*t.a[k][j])%mod; 33 res.a[i][j]%=mod; 34 } 35 } 36 } 37 return res; 38 } 39 }; 40 int main(){ 41 ll n; 42 cin>>n; 43 node p,ans,e; 44 for(int i=1;i<=4;i++){ 45 for(int j=1;j<=4;j++){ 46 p.a[i][j]=0; 47 ans.a[i][j]=0; 48 e.a[i][j]=0; 49 } 50 } 51 for(int i=1;i<=4;i++)p.a[1][i]=1; 52 p.a[2][1]=p.a[3][3]=p.a[3][4]=p.a[4][3]=1; 53 ans.a[1][1]=ans.a[3][1]=1; 54 for(int i=1;i<=4;i++)e.a[i][i]=1; 55 if(n==1){ 56 printf("0 "); 57 return 0; 58 } 59 if(n==2){ 60 printf("1 "); 61 return 0; 62 } 63 n-=2; 64 while(n){ 65 if(n&1)e=e*p; 66 p=p*p; 67 n>>=1; 68 } 69 ans=e*ans; 70 cout<<ans.a[1][1]<<endl; 71 }