+++
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](https://codeforces.com/contest/1106/problem/F)"
authors = ["xry111"]
+++

# 问题描述

[原题目链接](https://codeforces.com/contest/1106/problem/F)。

已知 $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][1]
知道 $\\omega = 3$，以此可以定义 $\\{0, \cdots, p-2\\}$ 与
$\\{1, \cdots, p-1\\}$ 之间的双射。正映射就是我们很熟悉的

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

逆映射就是离散对数：

$$f^{-1}(y) = Ind\_3 (y)$$

[1]: https://www.wolframalpha.com/input/?i=primitive+root+of+998244353

众所周知，可以用[大步小步法][BSGS]在 $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})$$

[中国剩余定理][CRT]告诉我们原同余方程的解和拆分得到同余方程组的解一一对应，
所以只要解拆分出来的这三个方程即可。对于前两个方程，特判 $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$。

[BSGS]: https://en.wikipedia.org/wiki/Baby-step_giant-step
[CRT]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

[参考代码](https://codeforces.com/contest/1106/submission/49271312)。