分式分解，给小朋友们做现场的表演

Elegia · 2020-04-13 23:22:28 · 个人记录

小朋友们大家好！还记得我是谁吗？对了！我就是为忆哀配音的演员，忆艾！这天我来到了秦皇岛，为小朋友们做现场的爆零表演，然后有个小朋友突然举手，老远就看到一双兔耳朵：「求助：线性递推」，小粉兔抱着我呀，非常高兴！

好，我们现在来看看，已知 \deg P < \deg Q，\displaystyle Q(x) = \prod_{i=1}^r (1-a_i x)^{k_i}，我们记 \sum k_i = n，我们知道其实有唯一分解式：

\frac{P}{Q} = \sum _{i=1}^r \frac{R_i (x)}{(1-a_ix)^{k_i}} \quad \deg R_i < k_i

我们能够从这个东西中读出 [x^t]P/Q 的通项，那就是

\sum_{i=1}^r f_i(t) a_i^t \quad \deg f_i < k_i

好，其实我们把它算出来之后，我们可以在 \Theta(n + r\log t) 的时间内算出一项的值（利用组合数计算，快速幂）

我们接下来记 q_i(x) = (1-a_ix)^{k_i}，接下来的推导也只需要 q_i 之间互质。

那么我们怎么计算 R 呢，注意到求和之后进行通分，R_i 部分对 P 的贡献就是 V_i(x) = R_i(x) Q(x)/q_i(x)，注意到 P(x) \bmod q_i(x) = V_i(x) \bmod q_i(x)，这是因为其他的 V_j(x) 都包含 q_i(x) 这个因子。那么我们就懂了，R_i(x) = P(x) \left[Q(x)/q_i(x) \bmod q_i(x)\right]^{-1} \bmod q_i(x)。

如果不用 FFT，我们考虑对 Q(x)/q_i(x) 可以在 \Theta(nk) 时间计算，求逆可通过多项式辗转相除在 \Theta(nk) 时间计算，总共时间就是 \Theta(nk)，因此总开销是 \Theta(n^2)。
如果用 FFT，我们容易通过分治树得到 P(x) \bmod q_i(x) 和 Q(x)/q_i(x) \bmod q_i(x) 这两部分，在 \Theta(n\log n\log r) 时间内。接下来考虑求逆，~~我们可以通过折半欧几里得在 \Theta(n\log ^2 n) 内完成。~~开个玩笑，大家应该也大都没写过多项式欧几里得，我们考虑这里 q_i(x) = (1-a_i x)^{k_i}，做变量代换 t = 1 - a_i x，容易发现这一变换是保度数的，因此在这一变换下我们只需求 P(\frac{1-t}{a_i}) 在 \bmod t^{k_i} 意义下的逆，然后变换回去就是对应的逆，这一部分的总共时间开销是 \Theta(n\log n)。

综上，本问题得到较完满的解答。