description
定义数列 \(f\)，当 \(i>k\) 时，\(f_i=\prod\limits_{j=1}^k f_{i-j}^{b_k}\)
模 998244353 。
已知数组 \(b\) 且 \(f_1,f_2,\dots,f_{k-1}\) 均等于 1，给定 \(n,m\) 。
求任意一个合法的 \(f_k\) 的取值（在 \([0,998244352]\) 间），使得 \(f_n=m\)
无解输出 -1
\(k\leq 100,n\leq 10^9\)
solution
观察一下 \(f_i=\prod\limits_{j=1}^k f_{i-j}^{b_k}\) 这个式子，因为 \(f_1=f_2=\dots=f_{k-1}=1\) 所以 \(f_i\) 一定能表示成 \(f_k^x\) 的形式，设 \(g_i=x\)。则 \(g_i=\sum\limits_{j=1}^kg(i-j)\)。
于是可以矩阵快速幂求出 \(g_n\)
那么问题就变成了解方程 \(x^{g_n} \equiv m \pmod {998244353}\)
对于这样的方程：\(x^{a} \equiv b \pmod {998244353}\)
由于 998244353 是奇素数，所以每个 \([1,998244352]\) 中的整数都可以用 998244353 的原根的次幂表示。
设其原根为 \(\rho\)，对于 \(a=\rho ^x\)，称 \(a\) 的指标（离散对数） \(I(a)=x\)。
对于方程 \(x^{a} \equiv b \pmod {998244353}\)，我们用 BSGS 求出 \(I(b)\)，根据对数的运算法则有 \(aI(x)=I(b) \pmod {\varphi(998244353)}\)，用 exgcd 解出 \(I(x)\) 即可得到 \(x\)。
多个地方需要注意判无解。
时间复杂度 \(O(k^3\log n+\sqrt{998244353}+\log998244353)\)
hint
998244353 的最小原根是 3。
注意矩阵快速幂的模数是 \(\varphi(998244353)=998244352\)。
啊啊啊，这题模拟赛赛后两分钟过……场上 exgcd 求解写挂了，难蚌