对于多项式 \(f(x)\)，求满足 \(f(x)g(x) = 1\pmod {x^n}\) 的 \(g(x)\)。
其中取模的意义在于丢掉第 \(n\) 项后面的系数不管。
一些 dp 题可能有形如 \(f_i= \sum_j g_j f_{i-j}\) 的卷积形式转移，可以写成多项式然后除过来求逆，即可得到最终答案，这种时候也可以分治 NTT/FFT，但是复杂度多一个 \(\log\)。当然生成函数的系数也可以用它求。
考虑一个显然的引理：
\[f(x)g(x)=1\pmod{x^n}\rightarrow f(x)g(x)=1\pmod{x^m} \]其中 \(m \le n\)。证明就是多项式乘法是卷积形式，高次项的去除不会影响低次项系数。
接着推(设 \(g(x)\) 是 \(f(x)\) 在 \(\pmod{x^{\lceil\frac{n}{2}\rceil}}\) 意义下的逆元，\(b(x)\) 是 \(f(x)\) 在 \(\pmod{x^n}\) 意义下的逆元)：
\[b(x)=g(x)\pmod{x^{\lceil\frac{n}{2}\rceil}} \]\[(b(x)-g(x))^2=0\pmod{x^{n}} \]\[b(x)^2-2b(x)g(x)+g(x)^2 = 0 \pmod{x^n} \]发现这时把 \(f(x)\) 乘进去，将能消掉的消掉，有
\[b(x)-2g(x)+f(x)g(x)^2=0 \pmod{x^n} \]也即
\[b(x)=g(x)(2-f(x)g(x)) \]使用多项式乘法(NTT/FFT)即可。
复杂度 \(O(n\log n)\)。
标签：求逆,系数,pmod,多项式,复杂度,消掉 From： https://www.cnblogs.com/infinities/p/17107773.html