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_kequiv h_n(modP-1))的一元同余方程,用exgcd解出(h_k),
exgcd还有好多用途 - 然后(f_kequiv3^{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);
}