方程的根通过移项可以得到低次向高次的线性递推,通过变形目标式得到目标式的线性递推,最后用矩阵乘法快速幂处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod =998244353;
int nn=3;
const int maxn=10;
struct mat{
ll m[maxn][maxn];
mat(){
memset(m,0,sizeof(m));
}
mat operator * (const mat b) const {
mat ans;
for(int i=1;i<=nn;++i)
{
for(int j=1;j<=nn;++j)
{
for(int k=1;k<=nn;++k)
{
ans.m[i][j]+=m[i][k]*b.m[k][j];
ans.m[i][j]%=mod;
ans.m[i][j]+=mod;
ans.m[i][j]%=mod;
}
}
}
return ans;
}
};
mat pow_mat(mat a,ll b)
{
mat ans;
for(int i=1;i<=nn;++i)
{
ans.m[i][i]=1;
}
while(b)
{
if(b&1)
ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main ()
{
ll s,t,u,n,mm;
cin>>n>>mm>>s>>t>>u;
mat a,b,ans;
nn=3;
a.m[1][1]=s;
a.m[1][2]=-t;
a.m[1][3]=u;
a.m[2][1]=1;
a.m[3][2]=1;
b.m[1][1]=s;
b.m[1][2]=1;
b.m[2][1]=-t;
b.m[2][3]=1;
b.m[3][1]=u;
ans.m[1][2]=-1;
ans.m[2][1]=1;
a=pow_mat(a,n);
b=pow_mat(b,mm);
a=a*ans;
a=a*b;
cout<<a.m[nn][nn];
return 0;
}
|