AC. 梦想

frank_c1

多项式运算小结

发布于2016年04月01日 | 暂无评论 | 3,178阅读 | 高等数学

多项式可以加减乘,这是基本常识。然而,多项式还支持除法、乘方、开方、求对数等等运算,这可实在是有些神奇。于是在此小结一下多项式的诸多运算。在接下来的叙述中,定义多项式A(x) = \sum_{i=0}^{n} {a_i x^i}

为方便叙述,在下列所有运算中,多项式的运算均定义在\pmod {x ^ n}意义下,整数的运算均定义在\pmod P意义下,其中P是一个大质数。在程序实现中,取P = 998244353

加法/减法

给定多项式A(x),B(x),求A(x) + B(x)A(x) - B(x)

将多项式的对应项直接相加减即可。时间复杂度O(n)

乘法

给定多项式A(x),B(x),求A(x)B(x)

对于普通的多项式乘法,可以用经典的FFT或分治乘法实现。在模特殊的大质数P时可以使用NTT,一般要求P = c \cdot 2 ^ k + 1,如UOJ模数998244353 = 7 \times 17 \times 2 ^ {23} + 1。时间复杂度O(n \log n)

求导/积分

给定多项式A(x),求A'(x)\int_{0} ^ {\infty} {A(x)}

根据定义逐项求导/积分即可,具体过程见微积分基本定理。时间复杂度O(n)

多项式的一些比较正常的运算就到此结束了。接下来是一些有趣的姿势。

逆元

给定多项式A(x),求A^{-1}(x) \pmod {x ^ n}

A^{-1}(x)称为A(x)的逆元,满足A(x)A^{-1}(x) \equiv 1 \pmod {x ^ n}

首先考虑A^{-1}(x) \pmod {x},显然有A^{-1}(x) \equiv a_0 \pmod {x}

考虑倍增。如果我们知道了A^{-1}(x) \pmod {x ^ k},怎样得到A^{-1}(x) \pmod {x ^ {2k}}呢?

B(x) = A^{-1}(x) \pmod {x ^ k},C(x) = A^{-1}(x) \pmod {x ^ {2k}},显然有

A(x)B(x) \equiv 1 \pmod {x ^ k} \\ A(x)C(x) \equiv 1 \pmod {x ^ k}

则有

B(x) - C(x) \equiv 0 \pmod {x ^ k}

可以推得

(B(x) - C(x)) ^ 2 = B^2(x) - 2B(x)C(x) + C^2(x) \equiv 0 \pmod {x ^ {2k}} \Rightarrow \\ C(x) \equiv 2B(x) + A(x)B^2(x) \pmod {x ^ {2k}}

上述过程可以用FFT或NTT实现。如此,就可以在O(\log n)次迭代后求出多项式的逆元。根据主定理有

T(n) = T(n/2) + O(n \log n) = O(n \log n)

于是时间复杂度是O(n \log n)。在此膜拜一下Miskcoo神犇的Blog

除法/模

给定n次多项式A(x)m次多项式B(x),求\frac{A(x)} {B(x)}

//似乎没有这么简单....我重更一下。

题目所求即为A(x) B^{-1}(x),我们只需要求B(x)的逆元即可。时间复杂度O(n \log n)

对数

给定多项式A(x),求\ln(A(x))

B(x) = \ln(A(x)),根据链式法则有

B'(x) = (\ln(A(x))' = \ln'(A(x))A'(x) = \frac{A'(x)} {A(x)}

于是只需要求一次A(x)的逆元,与A'(x)相乘得到B'(x),再积分还原B(x)即可。时间复杂度O(n \log n)

注意,在求对数时,必须保证a_0 = 1

指数

给定多项式A(x),求e ^ {A(x)},即\exp(A(x))

f(x) = e ^ {A(x)}。根据定义,可以列出方程g(f(x)) = \ln(f(x)) - A(x) = 0

考虑牛顿迭代法。首先,易知f(x) = e ^ {A(x)} \equiv 1 \pmod {x}

接下来我们考虑怎样由f_0(x) \pmod {x ^ k}推出f(x) \pmod {x ^ {2k}}

显然有f_0(x) \equiv f(x) \pmod {x ^ k}。在f_0(x)处泰勒展开,可得

\begin{aligned} g(f(x)) &= 0 \\ &= g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) + g''(f_0(x))(f(x) - f_0(x)) ^ 2 + ... \\ &= g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) \pmod {x ^ {2k}} \end{aligned}

则有

f(x) = f_0(x) - \frac {g(f_0(x))} {g'(f_0(x))} \pmod {x ^ {2k}}

注意到泰勒展开时,由于f(x) - f_0(x) \equiv 0 \pmod {x ^ {sk}} \; (s \ge 2),大于等于二次的项均可以被消去,于是剩下的式子就十分简洁明了。将方程g(f(x)) = \ln(f(x)) - A(x)代入上式,得

\begin{aligned} f(x) &= f_0(x) - \frac{\ln(f_0(x)) - A(x)} {\frac{1} {f_0(x)}} \\ &= f_0(x)(1 - \ln(f_0(x)) + A(x)) \pmod {x ^ {2k}} \end{aligned}

根据主定理有T(n) = T(n/2) + O(n \log n) = O(n \log n),于是时间复杂度O(n \log n)

乘方

给定多项式A(x),求A(x) ^ k的前n次项。

方法1:快速幂

考虑像一般整数的快速幂一样,每一轮迭代FFT一次并舍去多余项。时间复杂度O(n \log n \log k)

方法2:指对变换

由指数函数和对数函数的性质,有

A(x) ^ k = e ^ {k \ln A(x)}

于是时间复杂度就是O(n \log n)。注意,在这种方法中,由于需要对多项式求对数,则须a_0 = 1。若a_0 \neq 1怎么办呢?我们可以稍微转化一下。设A(x)的最低次项为a_d x ^ d,则有

A(x) ^ k = a_d x ^ {kd} (\frac{A(x)} {a_d x ^ d}) ^ k

此时括号内的式子一定满足a_0 = 1,满足对数运算条件。

开方

给定多项式A(x),求\sqrt[k]{A(x)}

类似乘方运算的方法2,我们有

\sqrt[k]{A(x)} = A(x) ^ {\frac{1} {k}} = e ^ {\frac{\ln A(x)} {k}}

时间复杂度同样是O(n \log n)。对于常数项不为1的情况,同样有

A(x) ^ {\frac{1} {k}} = a_d x ^ {\frac{d}{k}} (\frac{A(x)} {a_d x ^ d}) ^ {\frac{1} {k}}

注意到必须满足d | k才可以。

文中许多思路和推导过程摘自JCVB的论文《生成函数的运算和组合计数问题》。