点此看题
数论算法大杂烩， i i i了 i i i了
虽然我们不知道 f k f_k fk是多少，但是我们知道 f n f_n fn和 f k f_k fk的关系，记 f k f_k fk的指数为 1 1 1，发现我们对于上述递推式很容易算出 f n f_n fn的指数，用矩阵乘法（别告诉我这个你不会），算出来的指数假设是 n n n，那么（ p = 998244353 p=998244353 p=998244353）： f n = f k n m o d p f_n=f_k^n\mod p fn=fknmodp还是很难，这意味着我们要解一个高次剩余方程（我以前连二次的都不怎么会），但是由于模数固定且特殊，我们知道 998244353 998244353 998244353的原根是 3 3 3，所以可以改写成： f n = 3 a n m o d p f_n=3^{an}\mod p fn=3anmodp那么 a n an an是可以用 b s g s \tt bsgs bsgs求出的，那我们想算 a a a，可以考虑去算 n n n的逆元，首先我们要确定逆元的模式。 a n an an本质是模 p − 1 p-1 p−1的， n n n我们也要求它模 p − 1 p-1 p−1的逆元（都是指数嘛），由于 p − 1 p-1 p−1不是质数，所以我们只能用 e x g c d \tt exgcd exgcd求逆元。
值得注意的是，平常我们求逆元都是要在被求逆数和模数互质的情况下进行的，但是对于此题如果被求逆数和模数不互质就意味着无解吗？不是这样的，考虑最大公因数是 d d d的实际意义，如下： n × i n v n = d m o d ( p − 1 ) n\times inv_n=d\mod (p-1) n×invn=dmod(p−1)考虑 a n an an乘上 i n v n inv_n invn后消去了 n n n留下了 d d d，我们把这个留下的 d d d除掉就得到了 a a a，所以只需要保证 a n an an是 d d d的倍数就行了。
#include <cstdio> #include <cstring> #include <cmath> #include <map> using namespace std; const int p = 998244353; const int MOD = p-1; const int M = 105; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,k,t,x,y; struct Matrix { int n,m,a[M][M]; Matrix() {n=m=0;memset(a,0,sizeof a);} void clear() {memset(a,0,sizeof a);} Matrix operator * (const Matrix &b) const { Matrix r; r.n=n;r.m=b.m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=b.m;k++) r.a[i][k]=(r.a[i][k]+a[i][j]*b.a[j][k])%MOD; return r; } void print() { for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) printf("%lld ",a[i][j]); } }A; Matrix qkpow(Matrix a,int b) { Matrix r; r.n=r.m=k; for(int i=1;i<=k;i++) r.a[i][i]=1; while(b>0) { if(b&1) r=r*a; a=a*a; b>>=1; } return r; } int bsgs(int a,int b) { int m=sqrt(p)+1,t=1,tt=1; map<int,int> mp; for(int i=0;i<m;i++) { mp[b*t%p]=i; t=t*a%p; } for(int i=1;i<=m;i++) { tt=tt*t%p; if(mp[tt]) return i*m-mp[tt]; } return 0; } int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1;y=0; return a; } int d=exgcd(b,a%b,y,x); y-=x*(a/b); return d; } int fast(int a,int b) { int r=1; while(b>0) { if(b&1) r=r*a%p; a=a*a%p; b>>=1; } return r; } signed main() { k=read(); A.n=A.m=k; for(int i=1;i<=k;i++) A.a[1][i]=read(); for(int i=1;i<=k;i++) A.a[i+1][i]=1; n=read();m=read(); A=qkpow(A,n-k);n=A.a[1][1]; t=bsgs(3,m); int d=exgcd(n,MOD,x,y); x=(x%MOD+MOD)%MOD; if(t%d) puts("-1"); else { t/=d;//如果有公因数也是可以有逆的，t先踢掉这个公因数 printf("%lld\n",fast(3,t*x%MOD)); } } /* m=3^an %p bsgs: a^{tb-r}=b a^{tm}=b*a^r mod p 0 0 0 0 1 4 */