把操作写成矩阵，显然要求的是 $$ \begin{bmatrix} [x^0]F_1(x)&[x^1]F_1(x)&\cdots&[x^N]F_1(x)\\ [x^0]F_2(x)&[x^1]F_2(x)&\cdots&[x^N]F_2(x)\\ \vdots&\vdots&\ddots&\vdots\\ [x^0]F_N(x)&[x^1]F_N(x)&\cdots&[x^N]F_N(x)\\ \end{bmatrix}\begin{bmatrix} A_1^0&A_2^0&\cdots&A_N^0\\ A_1^1&A_2^1&\cdots&A_N^1\\ \vdots&\vdots&\ddots&\vdots\\ A_1^N&A_2^N&\cdots&A_N^N\\ \end{bmatrix}\begin{bmatrix} C_1\\ C_2\\ \vdots\\ C_N \end{bmatrix} $$ 其中 $F_n(x)=\prod_{i=1}^n(x+B_i)$。

其中第一步就是求 $\sum_{i=1}^N\frac{C_i}{1-A_i}$ 的前 $N+1$ 项系数，可以用分治 FFT 在 $O(N\log^2N)$ 时间内解决。

第二步可以利用转置原理。注意到其转置就是给定 $D_1,D_2,\ldots,D_N$，求 $\sum_{i=1}^ND_iF_i(x)$，可以用分治 FFT 在 $O(N\log^2N)$ 时间内解决，故原问题也可以在相同时间内解决。