多项式全家桶(持续更新中)

更多代码请移步一些模板

多项式乘法

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\)。

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

上一篇:LG题解 P7843 「PMOI-4」猜排列


下一篇:多项式求逆