ToB企服应用市场:ToB评测及商务社交产业平台

标题: 重修多项式 [打印本页]

作者: 写过一篇 时间: 2022-8-11 05:00
标题: 重修多项式
前置芝士
乘法逆

题面

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\)，答案为 \([x^0]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}\]
我们就得到了递推式。
牛迭

Konata：多项式牛顿迭代法，不止用来求逆用的。

Konata：求逆的话就是在上面证明基础上直接用就好了。
代码 / 时间复杂度

注意多项式项数 / 边界等细节，可看注释。
record
时间：

\[T(n)=T(\frac{n}{2})+n\log n\]
由主定理，时间复杂度为 \(O(n\log n)\)。
本文作者为小蒟蒻：ShaoJia
转载请注明原文链接。
码字不易，求关照，谢谢！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)