重修 多项式
前置芝士乘法逆
题面
P4238 【模板】多项式乘法逆
给定一个多项式 \(F(x)\)，请求出一个多项式 \(G(x)\)， 满足 \(F(x) * G(x) \equiv 1 \pmod{x^n}\)。
系数对 \(998244353\) 取模。
为方便 NTT 和倍增，不妨设 \(n\) 为 \(2\) 的幂。最后将 \(G(x)\) 的 \(0,\dots,(n-1)\) 次项输出即可。
最后推出的柿子是一样的，但是我们有两种证明方法。
倍增
首先，若 \(n=1\)，答案为 \(F(x)\) 的乘法逆元。
假设我们求出了 \(\bmod x^{n/2}\) 的逆，设为 \(G'(x)\)。
接下来就是柿子环节
\[\begin{aligned}F*G'&\equiv 1\pmod{x^{n/2}}\\F*G&\equiv 1\pmod{x^n}\\G-G'&\equiv 0\pmod{x^{n/2}}\\(G-G')^2&\equiv 0\pmod{x^n}\\G^2-2GG'+G'^2&\equiv 0\pmod{x^n}\\F(G^2-2GG'+G'^2)&\equiv 0\pmod{x^n}\\G-2G'+FG'^2&\equiv 0\pmod{x^n}\\G&\equiv (2-FG')G'\pmod{x^n}\end{aligned}\]
我们就得到了递推式。
牛迭
https://img2022.cnblogs.com/blog/2213867/202206/2213867-20220625160042031-1529759970.png
Konata：多项式牛顿迭代法，不止用来求逆用的。
https://img2022.cnblogs.com/blog/2213867/202206/2213867-20220625160048822-454467183.png
Konata：求逆的话就是在上面证明基础上直接用就好了。
代码 / 时间复杂度
注意多项式项数 / 边界等细节，可看注释。
record
时间：
\
由主定理，时间复杂度为 \(O(n\log n)\)。
本文作者为小蒟蒻：ShaoJia
转载请注明原文链接。
码字不易，求关照，谢谢！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]