更多代码请移步一些模板。

多项式乘法

FFT/NTT，详见别人的博客。由于有些复杂，作者懒得写了。而且写了也对作者没什么意义。

多项式求逆

对多项式\(f(x)\) 求多项式 \(g(x)\) 使得 \(f(x)\cdot g(x)\equiv 1\pmod {x^n}\)

这里的\(\pmod {x^n}\) 的意义其实就是“\(x\) 的次数最低的 \(n\) 项”

做法

考虑使用倍增。设 \(h(x)\cdot f(x)\equiv1\pmod {x^{\lceil\frac{x}{2}\rceil}}\)。那么：

\[\because f(x)\cdot g(x)\equiv 1\pmod {x^{\lceil\frac{x}{2}\rceil}}\\\therefore f(x)(h(x)-g(x))\equiv 0\pmod {x^{\lceil\frac{x}{2}\rceil}} \]

观察 \(f(x)(h(x)-g(x))\) 的常数项，由于 \(f(x)\) 的常数项不为 0，所以 \(h(x)-g(x)\) 的常数项必然为 0（根据 \(f(x)(h(x)-g(x))\)的后 \(n\) 项均为 0 可知）. 再观察 \(f(x)(h(x)-g(x))\) 的一次项，一次项是 \(f(x)\) 的常数项 * \(h(x)-g(x)\) 的一次项 + \(h(x)-g(x)\) 的常数项 * \(f(x)\) 的一次项。所以必然 \(h(x)-g(x)\) 的一次项也为 0.以此类推，\(h(x)-g(x)\equiv 0\pmod {x^{\lceil \frac{n}{2}\rceil}}\) 。

考虑到这是在 \(\pmod x^{\lceil \frac{n}{2}\rceil}\) 意义下的，那么平方就可以转化到 \(\pmod {x^n}\) 意义下的。于是有 \((h(x)-g(x))^2\equiv 0\pmod {x^{ n}}\)。展开可以得到 \(h(x)^2-2h(x)g(x)+g(x)^2\equiv 0\pmod {x^n}\) 。

发现这是一个关于 \(g(x)\) 的二次式，但是却不能使用求根公式求它，那样还得套上一个多项式开根。。所以考虑利用 \(f(x)\cdot g(x)\equiv 1\pmod {x^n}\) ，将等式两边同时乘以 \(f(x)\)，这样可以将 \(g(x)\) 降次得到 \(g(x)\) 的最终表达式 \(g(x)=2h(x)-f(x)h(x)^2\)。

推这个的过程中用到了很多多项式变换的小技巧...