原理推导
按照多项式求逆中倍增的思想，可以写出这样的推导：假设我们已知在\(\pmod {x^{\lceil \frac{n}{2} \rceil}}\)求得\(B'(x)\)为当前的解，现在要步进至\(\pmod x^n\)，那么我们可以写出
按照多项式求逆中倍增的思想，可以写出这样的推导：假设我们已知在\(\pmod {x^{\lceil \frac{n}{2} \rceil}}\)求得\(B'(x)\)为当前的解，现在要步进至\(\pmod x^n\)，那么我们可以写出
首先知道：
\[E_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2} – \sum_{j = i + 1}^{n}\frac{q_j}{(i – j)^2} \]
现在要求所有的。我们可以考虑分成前后两个部分分别计算。先考虑前面的部分：
\[a_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2}\]
我们发现这一部分还是很好计算的：当多项式指数为\(i\)时，对应\(a_i\)，发现\(q_j\)和\((i – j)^2\)的下标相加恰好为\(i\)。正好是卷积的形式。后面那一个部分也可以直接这样算。