应该算是一个比较常见的套路了吧…模意义下乘法转加法然后就是个简单的递推题了。
题意描述：对于序列 ${f_n}$ 给出递推定义：$f_i=\prod_{j=1}^k f_{i-j}^{b_j} \qquad (mod \ p)$ ， 其中模数 $p=998244353$
接下来给出 $b_1,b_2,…,b_k$ 和 $f_1,f_2,…,f_{k-1}$ 以及 $f_n$ ，让你求 $f_k$ 的值，如果不存在则输出 $-1$ ，如果存在多解则输出其中任意一个。其中 $k \leq 100 , n \leq 10^9 ,f_1=f_2=…=f_{k-1}=1$ 。
首先看到这样的一个长得和线性递推有几分相似的递推公式以及较小的 $k$ 的范围，容易想到往矩阵快速幂的方向考虑。但因为连乘形式的递推式无法用矩阵直接表示，所以我们考虑把这个递推式进行转化。很自然的就会想到求对数。而由于这是在模意义下的整数数列，所以我们需要一个和对数性质很相像的东西——离散对数。
离散对数
我们都知道欧拉定理：若 $gcd(a,m)=1$ ,则 $a^{\phi(m)} \equiv 1(mod \ m)$ 。那么 $\phi(m)$ 是否是使得 $a^{x} \equiv 1(mod \ m)$ 成立的最小的正整数 $x$ 呢？事实上，当且仅当 $m$ 形如 $1,2,4,p,2p,p^n$ 时，存在 $a$ ，使得 $\phi(m)$ 是令 $a^{x} \equiv 1(mod \ m)$ 成立的最小的正整数。换句话说，我们能找到一个 $a$ ，使得 $a^0,a^1,a^2,a^3,…,a^{\phi(m)-1}$ 在 $mod \ m$ 意义下互不相同、并且均与 $m$ 互质。此时的 $a$ 我们称它为 $m$ 的原根。事实上，由于此时的 $a^0,a^1,a^2,a^3,…,a^{\phi(m)-1}$ 在 $mod \ m$ 意义下互不相同且均与 $m$ 互质，所以这 $\phi(m)$ 个数构成了与 $m$ 互质的 $\phi(m)$ 个数的一个排列。而当 $m$ 为质数 $p$ 时， $a^0,a^1,a^2,a^3,…,a^{p-2}$ 恰好就和 $1,2,3,…,p-1$ 形成了一一对应。换言之，对于任意一个数 $x\ (0<x<p)$ ，我们都能找到唯一的 $t\ (0 \leq t<p-1)$ ，使得在模 $p$ 意义下 $a^t=x$ 。
那么对于 $mod \ p$ 意义下的整数 $1,2,…,p-1$ 我们此时就有了一种新的表示方式，即：对于任意的 $1,2,…,p-1$ 之间的数 $k$ ，我们记满足 $a^x \equiv k\ (mod \ p)$ 的 $x$ 为 $ind_a(k) \ ( mod\ \phi(p))$ ，即 $k$ 在模 $p$ 意义下以 $a$ 为底的离散对数。
离散对数有着与对数相近的性质，比如：
$$
ind_a(xy) \equiv ind_a(x)+ind_a(y)\ (mod \ \phi(p)) \\
ind_a(x^y) \equiv y*ind_a(x)\ (mod \ \phi(p))
$$
求解一个数 $k$ 的离散对数本质上是在求解 $a^x \equiv k\ (mod \ p)$ 的解 $x$ ，用bsgs算法即可解决。
于是对于这道题，我们构造一个序列 ${g_n}$ ，他满足 $g_i = ind_a(f_i)$ ，其中 $a$ 为 $998244353$ 的一个原根。那么 ${g_n}$ 就有递推式：$g_i=\sum_{j=1}^k b_j*g_{i-j}$ 。这便成了一个线性递推的形式。我们可以构造矩阵：
$$
\left[ \begin{matrix}
0 & 0 & \cdots & 0 & b_k\\
1 & 0 & \cdots & 0 & b_{k-1}\\
0 & 1 & \cdots & 0 & b_{k-2}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & b_1
\end{matrix} \right]
$$
于是便有：
$$
\left[ \begin{matrix}
g_1 & g_2 & g_3 & \cdots & g_k
\end{matrix} \right] \left[ \begin{matrix}
0 & 0 & \cdots & 0 & b_k\\
1 & 0 & \cdots & 0 & b_{k-1}\\
0 & 1 & \cdots & 0 & b_{k-2}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & b_1
\end{matrix} \right] ^{n-1}=\left[ \begin{matrix}
g_n & g_{n+1} & g_{n+2} & \cdots & g_{n+k-1}
\end{matrix} \right] \,\,\left( mod\,\,\phi \left( p \right) \right)
$$
那么只要对这个矩阵求出其 $n-1$ 次幂后，利用其第一列元素即可得到一个关于 $g_1,g_2,…,g_k,g_n$ 的线性同余方程，用扩展欧几里得求解即可。
总结一下，首先考虑序列 ${g_n=ind_a(f_n)}$ ，然后对序列 ${g_n}$ 用矩阵快速幂的方法得到 $g_1,g_2,…,g_{k-1},g_k,g_n$ 的关系并求解，然后用快速幂从$g_n$ 得到 $f_n$ 即可。总复杂度为 $O(\sqrt{n}+k^3logn)$ 。
代码：
|
|
