U703133 惊鹊 出题报告

题面：https://www.luogu.com.cn/problem/U703133

题目从何而来？

这堆破玩意的原题是这样的：

\(T\) 组数据，设斐波那契数列 \(\{F_n\}\)，众所周知有个定理是 \(F_d|F_{nd}\)，求 \(k\pmod m\) 使得 \(kF_d\equiv F_{nd}\pmod m\)。不保证 \(F_d\) 对 \(m\)​ 有逆元。

\[1\leq T\leq10^5,1\leq n,d,m\leq 10^9 \]

结论1：

\[F_{a+b}=F_{a+1}F_b+F_{a}F_{b-1} \]

可以用二元归纳法证明，至于怎么正着推我特么怎么知道。

拆一下：

\[F_{nd}=F_{(n-1)d+1}F_d+F_{(n-1)d}F_{d-1}\\ F_{(n-1)d}=F_{(n-2)d+1}F_d+F_{(n-2)d}F_{d-1}\\ 则F_{nd}=(F_{(n-1)d+1}+F_{d-1}F_{(n-2)d+1})F_d+F_{d-1}^2F_{(n-2)d} \]

以此类推

\[F_{nd}=F_d\sum_{i=0}^{n-1}F_{d-1}^iF_{(n-i-1)d+1} \]

有点毒瘤啊

做法

所以这东西跟卷积毫无关系。

下面是我跟 gemini 老师学的，我只会推出来这个烂题但我不会做（

我们知道斐波那契递推矩阵是这样的：

\[A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\\ A^k = \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix} \]

则

\[A^{(n-i-1)d} = \begin{pmatrix} F_{(n-i-1)d+1} & F_{(n-i-1)d} \\ F_{(n-i-1)d} & F_{(n-i-1)d-1} \end{pmatrix} \]

那么

\[X=\sum_{i=0}^{n-1}F_{d-1}^iA^{(n-i-1)d}\\ \]

\(X_{0,0}\pmod m\)就是答案。

发挥极致的注意力：

\[A^d=\begin{pmatrix} F_{d+1} & F_d \\ F_d & F_{d-1} \end{pmatrix}=\begin{pmatrix} F_{d} & F_d \\ F_d & 0 \end{pmatrix}+\begin{pmatrix} F_{d-1} & 0 \\ 0 & F_{d-1} \end{pmatrix}=F_dA+F_{d-1}I \]

则得到一个非常神奇的恒等式：

\[A^d-F_dI=F_dA \]

注意到 \((x^n+y^n)=(x-y)(\sum_{i=0}^{n-1}x^iy^{n-1-i})\)，容易观察到与上面相像，代回 \(X\) 的定义式：

\[(A^d-F_dI)X=A^d-F_dI\sum_{i=0}^{n-1}F_{d-1}^iA^{(n-i-1)d}\\ F_dAX=A^n-F_{d-1}^nI \]

根据矩阵乘法规则，\((AX)_{1,0}=X_{0,0}\times A_{0,1}+X_{0,1}\times A_{1,1}=X_{0,0}\)，又有\((A^n-F_{d-1}^nI)_{1,0}=A^n_{0,0}=F_{nd}\)。

这就推回来了：

\[X_{0,0}\equiv \frac{F_{nd}}{F_{d}} \pmod m \]

不保证存在对 \(m\) 的逆元，那么这个怎么做呢？

结论2：

\[F_{nd} = L_d F_{(n-1)d} - (-1)^d F_{(n-2)d}，其中L_d 为第d个Lucas数，L_d = F_{d-1} + F_{d+1} \]

\(F_d\) 是常数，设 \(U_d=\frac{F_{nd}}{F_{d}}\)，它也必然满足 \(U_{nd} = L_d U_{(n-1)d} - (-1)^d U_{(n-2)d}\)。

容易构造矩阵，注意在模 \(m\) 下 \(-(-1)^d\) 不能直接填进去，设 \(C=-(-1)^d\bmod m\)：

\[\begin{pmatrix} U_n \\ U_{n-1} \end{pmatrix} = \begin{pmatrix} L_d & C \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

两次矩阵快速幂，时间复杂度 \(O(T(\log n+\log d))\)。