A.幸福
- 考场上没想起矩阵，写了个 \(\mathtt{O(n)}\) 的暴力，得 \(\mathtt{70pts}\) ；
Solution
-
矩阵乘法。对 \(F_n\) 进行化简，就可以化得一个式子： \(F_n=F_{n-1}+F_{n-2}+f_n\)，其中 \(f_n\) 表示斐波那契数列的第 \(n\) 项。
-
然而这样还是不能求和。
解决方案为将 \(sum\) 也放进矩阵里。
于是设计答案矩阵构成为 \(\begin{bmatrix}sum_n&F_n&F_{n-1}&f_{n+1}&f_n\end{bmatrix}\)，则每次转移时将 \(F_{n+1}\) 算出再累加到 \(sum_n\) 中，即可得到 \(sum_{n+1}\)。 -
与这个矩阵对应的转移矩阵为：
\(\begin{bmatrix}1&0&0&0&0\\1&1&1&0&0\\1&1&0&0&0\\1&1&0&1&1\\0&0&0&1&0\end{bmatrix}\)
AC 矩阵乘法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
struct memr{
ll x[10][10];
int a,b;
memr operator*(const memr &_)const{
memr cnt;
memset(cnt.x,0,sizeof(cnt.x));
cnt.a=a,cnt.b=_.b;
for(int i=1;i<=a;++i)
for(int j=1;j<=_.b;++j)
for(int k=1;k<=b;++k)
(cnt.x[i][j]+=1ll*x[i][k]*_.x[k][j]%mod)%=mod;
return cnt;
}
};
memr ksm(ll y){
memr dx;
dx.a=dx.b=5;
memset(dx.x,0,sizeof(dx.x));
dx.x[1][1]=dx.x[2][1]=dx.x[3][1]=dx.x[4][1]=1;
dx.x[2][2]=dx.x[3][2]=dx.x[4][2]=1;
dx.x[2][3]=dx.x[4][4]=dx.x[4][5]=dx.x[5][4]=1;
memr cnt;
cnt.a=cnt.b=5;
for(int i=1;i<6;++i)
for(int j=1;j<6;++j)
cnt.x[i][j]=(i==j);
for(;y;y>>=1,dx=dx*dx)
if(y&1)
cnt=cnt*dx;
return cnt;
}
ll n;
int main(){
scanf("%lld",&n);
if(n==0){
printf("%d",1);
return 0;
}
memr ans;
ans.a=1,ans.b=5;
memset(ans.x,0,sizeof(ans.x));
ans.x[1][1]=3;
ans.x[1][2]=2,ans.x[1][3]=ans.x[1][5]=1;
ans.x[1][4]=2;
ans=ans*ksm(n-1);
printf("%lld",ans.x[1][1]);
return 0;
}