P8979 「DTOI-4」白的 Fibonacci 口胡

· · 题解

偶然看到这题，就稍微回应一下题目提供者，虽然具体做法算是比较经典了。为方便表述，本文中记 F(1,0)=r_0，F(1,1)=r_1。

首先我们容易对 F(1,n) 建立关于 n 的生成函数：

F_1(x)=\frac{r_0+(r_1-r_0a)x}{1-ax-bx^2}

把递推式用生成函数表达：

F_k(x)=t_k x F_k(x)+ F_{k-1}(sx) F_k(x) = \frac{F_{k-1}(sx)}{1-t_kx}

递推的时候把 x 替换为 sx 的操作其实很好处理：

F_k(x)= \frac{r_0+(r_1-r_0a)s^{k-1}x}{1-as^{k-1}x-bs^{2k-2}x^2}\prod_{i=2}^k \frac{1}{1-t_is^{k-i}x}

大力分治乘然后做线性递推，时间复杂度 \Theta(k \log^2 k+k \log k \log n) 可以通过本题，但是还不够优秀。继续优化可以做到 \mathcal O(k \log^2 k+k \log n)，不过写起来比较复杂，看看就好。

EI 讲过，这种形式可以做分式分解。首先，我们把分母中的那个二次多项式做因式分解（可能需要扩域），我们的目标就是将这样一个形式的分式（注意一点，虽然乍一看分解后有 k+1 项，但是可能有重复，要记为重根）：

\frac{1}{Q(x)}=\prod_{i=1}^m \frac{1}{(1-q_ix)^{d_i}}

改写为

\sum_{i=1}^m \frac{P_i(x)}{(1-q_ix)^{d_i}}

这样一个形式就很容易提取一项系数了。

通分后可以得到这样一个结果（对于各 i \in [1,m]）：

\frac{P_i(x)Q(x)}{(1-q_ix)^{d_i}}\equiv 1 \pmod{(1-q_ix)^{d_i}}

所以我们只需要求出各 \dfrac{Q(x)}{(1-q_ix)^{d_i}} \bmod (1-q_ix)^{d_i} 之后，再分别求出它们在模 (1-q_ix)^{d_i} 意义下的逆得到的便是 P_i(x)。

对于前者，可以分治处理：不要把它看作分式，它本身就是许多一次式的乘积，利用 F(x) \equiv (F(x) \bmod A(x)B(x)) \pmod {A(x)} 这一性质即可。

后者也比较简单，我另一篇题解中也有提到，就不复读了（

所以为什么参数的数据范围还要开到负数呢？