仅作为个人理解之用
来自 https://judge.yosupo.jp/submission/140699
首先product tree部分不变
我们考虑如何不使用形式幂级数求逆
注意到 如果对dft的点值求逆实际上是在对 x^lim-1 取模的意义下
实际上在这个意义下也是可做的
首先判掉所求点值在dft所用的单位根上的平凡情况(具体来说直接使用dft的结果即可)
那么不难证明这种情况下dft的点值均非0(可逆)
而p处点值即为 rev(f)/(1-px) (mod x^lim-1)[x^{lim-1}]
分治求即可