自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:44:17，当前版本为作者最后更新于2023-02-02 03:11:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

偶然看到这题，就稍微回应一下题目提供者，虽然具体做法算是比较经典了。为方便表述，本文中记 $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)}$ 这一性质即可。

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

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