多项式初等函数

Summary

在模 x^n 意义下，多项式同样能做求逆、开方、求对数、求指数等运算，它们是求解形式幂级数、组合计数等问题的基础工具。以多项式求逆为例：采用倍增，从满足模 x^(n/2) 的 B0 出发，用恒等式递推出模 x^n 的逆元 B 等于 B0 乘以 2 减 A 乘 B0，每一层套用一次 NTT，规模翻倍，总时间复杂度为 O(nlogn)。求对数 ln 借助求导后再积分实现，求指数 exp 则用牛顿迭代逐层逼近，开方同样可套牛顿迭代。配套例题为洛谷 P4238 多项式求逆。

参考资料

• 多项式初等函数 - OI Wiki

简介

在模 $x^n$ 意义下，可对多项式做求逆、开方、求对数、求指数等运算，它们是多项式进阶的基础。以 多项式求逆 为例：用倍增，从满足 $A B_0\equiv 1\pmod{x^{n/2}}$ 的 $B_0$ 推出模 $x^n$ 的逆 $B\equiv B_0(2-AB_0)\pmod{x^n}$，配合 NTT 总复杂度 $O(n\log n)$。$\ln$、$\exp$ 则借助求导、积分与牛顿迭代实现。

例题

洛谷 P4238 【模板】多项式乘法逆

给定一个 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 使 $F(x)G(x)\equiv 1\pmod{x^n}$，系数对 $998244353$ 取模。