blog/content/post/cf536-div2-f.md

+++ date = "2019-02-02T01:15:00+08:00" draft = false tags = [] title = "Problem F, CF Round #536 (Div. 2)" summary = "Solution of Lunar New Year and a Recursive Sequence" authors = ["xry111"] +++

问题描述

原题目链接。

已知 $p = 998244353$，数列 $\{f_i\}$ 满足

$$f_i = \left( \prod_{j=1}^k f_{i-j}^{b_j} \right) \mod p$$

且 $f_1 = f_2 = \cdots = f_{k-1} = 1$，$f_n = m$， 给定一组正的 $m$、$k$、$b_1 \cdots b_k$，求 $f_k$ 的任意一个可能值， 或报告没有可能的值。

解决方法

注意到 $p$ 是一个奇质数，根据原根定理知道存在 $\omega$ ，使得 $\omega^0, \cdots, \omega^{p-2}$ 两两不同。询问 WolframAlpha 知道 $\omega = 3$，以此可以定义 $\{0, \cdots, p-2\}$ 与 $\{1, \cdots, p-1\}$ 之间的双射。正映射就是我们很熟悉的

$$f(x) = 3^x \mod p$$

逆映射就是离散对数：

$$f^{-1}(y) = Ind_3 (y)$$

众所周知，可以用大步小步法在 $O(\sqrt{p})$ 的时间内求出离散对数。

下面令 $g_i = Ind_3 (f_i)$，那么递归式就等价于

$$g_i = \left( \sum_{j=1}^k b_j g_{i-j} \right) \mod (p-1)$$

在模 $p-1$ 意义下这是个线性递推数列，可以写成矩阵形式：

$$\gamma_n = \begin{bmatrix} g_n \\ g_{n-1} \\ \vdots \\ g_{n-k+2} \\ g_{n-k+1} \end{bmatrix} = \begin{bmatrix} b_1 & b_2 & \cdots & b_{k-1} & b_k \\ 1 & & & & \\ & 1 & & & \\ & & \ddots & & \\ & & & 1 & \\ \end{bmatrix} \begin{bmatrix} g_{n-1} \\ g_{n-2} \\ \vdots \\ g_{n-k+1} \\ g_{n-k} \end{bmatrix} $$

所以

$$\gamma_n = A^{n-k} \gamma_k = B \gamma_k$$

这里 $B = A^{n-k}$ 可以用矩阵快速幂求出。根据题目条件，

$$\gamma_k = [g_k, \cdots, g_1]^T = [g_k, 0, \cdots, 0]^T$$

可以看出 $g_n = B_{11} g_k$。其中 $g_n = Ind_3 (m)$ 可用大步小步法求出，$B$ 左上角的元素 $B_{11}$ 可用快速幂求出， 下面就要求 $g_k$。这里的问题在于，同余方程

$$g_n \equiv B_{11} g_k \quad~~ (mod \quad p-1)$$

中的模 $p-1 = 2^{23} \cdot 7 \cdot 17$ 是一个合数，所以不能用逆元。 我们可以用中国剩余定理把它拆成三个同余方程组成的方程组：

$$g_n \equiv B_{11} g_k \quad~~ (mod \quad 7)$$ $$g_n \equiv B_{11} g_k \quad~~ (mod \quad 17)$$ $$g_n \equiv B_{11} g_k \quad~~ (mod \quad 2^{23})$$

中国剩余定理告诉我们原同余方程的解和拆分得到同余方程组的解一一对应， 所以只要解拆分出来的这三个方程即可。对于前两个方程，特判 $B_{11}$ 余 $0$ 的情况（其中如果 $g_n$ 也余 $0$，则 $g_k$ 可以余任何数， 否则无解），然后用逆元即可。

对于第三个方程，由于 $B_{11}$ 可能与 $2^{23}$ 不互质，可能不存在逆元。 首先仍然特判 $B_{11}$ 余 $0$ 的情况，然后对 $g_n$ 和 $B_{11}$ 同时除以 $gcd(B_{11}, 2^{23})$。如果除不尽，说明无解。否则，新得到的方程中 $B_{11} / gcd(B_{11}, 2^{23})$ 一定与 $2^{23}$ 互质，就能用逆元了。

如果这三个方程中有一个或多个无解，则原同余方程一定无解。如果它们都有解， 就能用中国剩余定理得到原方程的一个解，即 $g_k$ 的一个可能值。 然后直接快速幂就能得到 $f_k = 3^{g_k} \mod p$。

参考代码。