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

 小朋友们大家好！还记得我是谁吗？对了！我就是为忆哀配音的演员，忆艾！这天我来到了秦皇岛，为小朋友们做现场的爆零表演，然后有个小朋友突然举手，老远就看到一双兔耳朵：[「求助：线性递推」](https://www.luogu.com.cn/discuss/show/212842)，小粉兔抱着我呀，非常高兴！ 好，我们现在来看看，已知 $\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)$。 综上，本问题得到较完满的解答。