对于多项式 \(f(x)=a_0+a_1x+a_2x^2+...+a_nx^n\)
若存在 \(g(x)=b_0+b_1x+b_2x^2+...+b_mx^m(m\le n)\) 使得 \(f(x)g(x)\equiv 1\pmod {x^m}\)，称 \(g(x)\) 为 \(f(x)\) 在模 \(x^m\) 下的逆元，记作 \(f^{-1}(x)\pmod {x^m}\)
多项式存在逆元的充要条件：\(a_0\) 在模 \(x^m\) 下有逆元。
多项式的逆元如果存在那么就唯一。
求取方法：
- 暴力。\(b_i=\frac{\sum_{j=0}^{i-1}a_{i-j}b_j}{a_0}\)
- 倍增 给定 \(f(x)\) 求 \(g(x)\)（关于 \(x^n\) 的逆元，其中 \(n\) 为 \(2\) 的幂）
若 \(f(x)g_n(x)\equiv 1\pmod {x^n}\) 成立，则有 \(f(x)g_{\frac{n}{2}}(x)\equiv 1\pmod {x^\frac{n}{2}}\)
那么 \(f(x)g_n(x)\equiv 1\pmod {x^\frac{n}{2}}\)
减一下，就有 \(f(x)(g_n(x)-g_{\frac{n}{2}}(x))\equiv 0\pmod {x^{\frac{n}{2}}}\)
也就是 \(g_n(x)-g_{\frac{n}{2}}(x))\equiv 0\pmod {x^{\frac{n}{2}}}\)
平方一下，\(g_n^2(x)-2g_ng_{\frac{n}{2}}+g_{\frac{n}{2}}^2(x)\equiv 0\pmod {x^n}\)
然后拿这个东西再去乘一个 \(f(x)\) 就有 \(f(x)g_n^2(x)-2f(x)g_n(x)g_{\frac{n}{2}}(x)+f(x)g_{\frac{n}{2}}^2(x)\equiv 0\pmod {x^n}\)
又由于 \(f(x)g(x)\equiv 1\pmod {x^n}\)
所以 \(g_n(x)=2g_{\frac{n}{2}}(x)-f(x)g^2_{\frac{n}{2}}(x)\pmod {x^n}\)
初始状态：\(g(x)\) 即为 \(a_0\) 在模 \(x\) 意义下的逆元。