https://codeforces.com/contest/1106/problem/F
题意
数列公式为\(f_i=(f^{b_1}_{i-1}*f^{b_2}_{i-2}*...*f^{b_k}_{i-k})\)mod\(P\),给出\(f_{1}...f_{k-1}\)和\(f_{n}\),求\(f_{k}\),其中\(P\)等于998244353
题解
- 3是998244353的离散对数,所以\(f^{b_1}_{i-1} \equiv 3^{h_i*b_1}(modP)\),怎么求离散对数
- 乘法转化为加法:\(h_{k+1}\equiv(h_{k}*b_1+...+h_{1}*b_k)mod(P-1)\),矩阵快速幂求出\(h_n\)(\(c*h_k(未知数)\)),\(mod(P-1)\)是欧拉降幂,因为\(h_n\)可能会很大
- 得到\(f_n=3^{h_n}\equiv m(modP)\),bsgs求出\(h_n\),有空填exbsgs的坑
- 于是得到\(c*h_k\equiv h_n(modP-1)\)的一元同余方程,用exgcd解出\(h_k\),exgcd还有好多用途
- 然后\(f_k\equiv3^{h_k}(modP)\)
代码
//vector矩阵快速幂板子
#include<bits/stdc++.h>
#define MOD 998244353
#define ll long long
#define vec vector<ll>
#define mat vector<vec>
using namespace std;
mat mul(mat &A,mat &B,ll mod){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int j=0;j<A.size();j++)
for(int k=0;k<A.size();k++)
C[i][j]+=A[i][k]*B[k][j]%mod,C[i][j]%=mod;
return C;
}
mat pw(mat &A,ll x,ll mod){
mat C(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)C[i][i]=1;
while(x){
if(x&1)C=mul(C,A,mod);
A=mul(A,A,mod);
x>>=1;
}
return C;
}
ll pw(ll bs,ll x,ll mod){
ll ans=1;
while(x){
if(x&1)ans=ans*bs%mod;
bs=bs*bs%mod;
x>>=1;
}
return ans;
}
ll bsgs(ll a,ll b,ll c){
ll m=ceil(sqrt(c));
map<ll,ll>mp;
ll bs=b,BS=pw(a,m,c);
for(int i=1;i<=m;i++){mp[bs]=i-1;bs=bs*a%c;}
bs=1;
for(int i=1;i<=m;i++){
if(mp[bs])return (i-1)*m-mp[bs];
bs=bs*BS%c;
}
return -1;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
ll d=a;
if(b==0)x=1,y=0;
else d=exgcd(b,a%b,y,x),y-=x*(a/b);
return d;
}
ll sol(ll a,ll b,ll m){
if(b==0)return 0;
ll g=__gcd(a,m);
if(b%g)return -1;
a/=g;b/=g;m/=g;
ll x,y;
g=exgcd(a,m,x,y);
x=x*b%m;
return (x+m)%m;
}
ll k,n,m,h,ans;
int main(){
cin>>k;
mat A(k,vec(k));
for(int i=0;i<k;i++)cin>>A[i][0];
for(int i=1;i<k;i++)A[i-1][i]=1;
cin>>n>>m;
A=pw(A,n-k,MOD-1);
h=bsgs(3,m,MOD);
ans=sol(A[0][0],h,MOD-1);
if(ans<0)cout<<-1;
else cout<<pw(3,ans,MOD);
}