多项式运算如何简化为疑问？

多项式的小总结 前置芝士🧀： FFT&NTT 微积分以及泰勒展开 多项式的各种运算 这些运算都是在模意义下进行的运算，但多项式的取模运算与整数的取模运算有些不同。 多项式对 \(x^n\) 取模的意思是舍弃 \(x^n\) 以及更高次的部分。 多项式求逆 对于一个多项式 \(A(x)\) ，如果存在 \(B(x)\) 使得 \[A(x)B(x)\equiv 1\pmod {x^n} \] 那么称 \(B(x)\) 为 \(A(x)\) 在 \(mod\: x^n\) 意义下的逆元 \((inverse\:element)\)，记作 \(A^{-1}(x)\)。 取模意义下，没有模数的逆元是没有意义的，因为不同的模数对应不一样的逆元。 推导 考虑用倍增法求解。 假如我们现在已经求出了 \(A(x)\) 在 \(mod\:x^{\frac{n}{2}}\) 意义下的逆元 \(B_0(x)\) ，即 \[A(x)B_0(x)\equiv 1\pmod {x^{\frac{n}{2}}} \] 而 \[\because A(x)B(x)\equiv 1\pmod {x^{\frac{x}{2}}} \] 两式相减并消去 \(A(x)\) 得 \[\therefore B(x)-B_0(x)\equiv 0\pmod {x^{\frac{n}{2}}} \] 再同时平方 \[B^2(x)-2B(x)B_0(x)+B_0^2(x)\equiv 0\pmod {x^n}B^2(x)-2B(x)B_0(x)+B_0^2(x)\equiv 0\pmod {x^n} \] 乘上 \(A(x)\)，即可消去 \(B(x)\) \[B(x)-2B_0(x)+A(x)B_0^2\equiv 0\pmod {x^n} \] 所以得到递推式 \[B(x)=B_0(x)(2-A(x)B_0(x))\pmod {x^n} \] 边界：当 \(n=1\) 时，\(B_0(x)\) 即为 \(A(x)\) 常数项的逆元。