视 $n+q$ 与 $n$ 同阶。

菊花的情况如何做到 $\Theta(n\log^2 n)$ 是熟知的：
问题可以泛化为给定分式列 $u_1(x)/v_1(x), u_2(x)/v_2(x), \dots, u_{n+q}(x)/v_{n+q}(x)$，其中 $\deg u_k(x),\deg v_k(x) = \Theta(1)$ 及向量 $a_0, a_1, a_2, \dots, a_n$，要求向量 $b_j = \sum_{i=0}^n a_i [x^i] \prod_{k=1}^j u_k(x)/v_k(x)$。
进行转置，则问题变为 $a_i = [x^i] \sum_{j=1}^{n+q} b_j \prod_{k=1}^j u_k(x)/v_k(x)$，即求该分式列前缀积的带权求和。只需要分治 NTT 即可。

对于一般的情况，我们只需要使用动态 DP 的任意一种常用手法即可。这里以链分治为例：重链剖分后将整个问题进行离线，然后自下而上处理各重链，处理每条重链时在每个点处计算先前提到的子问题，而重链上的转移可以用 $\Theta(1)$ 个信息的线性变换的复合表示。

总复杂度 $\Theta(n \log^2 n + q \log^3 n)$。