学习笔记：多项式全家桶

· · 个人记录

前言

搞完多项式乘法之后，其实我就想把多项式的这一堆都做了，但是鸽了很久都没动。。
最近正在一点点啃，笔记都会记在这里。

\text{Part1 万恶之源——多项式乘法}

在我的这篇 blog 里，较为详细地讲了 FFT，借由这个算法，可以实现 \Theta(n\log n) 的多项式乘法（卷积）。
可是 FFT 要用到复数，这使得精度没办法保障，而且还不能取模。
那有没有别的方法解决这个问题呢？
答案很自然地是肯定的。

在数论中，有一个叫做原根的东西。简单来说，质数 p 的原根定义是这样的：
若整数 g^i\bmod p 的结果两两不同，且 g\in[2,p-1]，i\in[1,p-1]，那么 g 就是 p 的原根。
比如质数 998244353 的最小原根就是 3。

这个原根的用处就在于，它有着和 FFT 中的单位根 \omega 相似的性质！
利用这个性质我们就可以实现 快速数论变换NTT（\text{Number Theory Transform}）

在 FFT 的代码中要计算 \omega_n^k 时，对应到 NTT 中就是 g^{\frac{p-1}{n}k}。这也很好理解，g^{\frac{p-1}{n}} 的 0 到 n-1 次方各不相同，且 n 次方为 1，这就和单位根完美地对应上了。

一般我们取 p=998244353 \ , \ g=3，方便计算。
然后我们就能打出 NTT 的板子了，和 FFT 极为相近: 

void NTT(int *a,int type,int lim){
    for(int i=0;i<=lim;++i){
        if(i>=rev[i]) continue;
        swap(a[i],a[rev[i]]); //这里的 rev 同 FFT 中的翻转数组
    }
    for(int mid=1;mid<lim;mid<<=1){
        int rt = power(3,(p-1)/(mid<<1)); //上述的单位根计算方法
        if(type==-1) rt = power(rt,p-2); //如果是逆变换，单位根要变逆元
        int r = mid<<1;
        for(int j=0;j<lim;j+=r){
            int w = 1;
            for(int k=0;k<mid;++k){
                int x = a[j+k];
                int y = (ll)w*a[j+k+mid]%p;
                a[j+k] = (x+y)%p;
                a[j+k+mid] = ((x-y)%p+p)%p;
                w = (ll)w*rt%p;
            }
        }
    }
}

用 NTT 计算多项式乘法，和 FFT 一样，最后出来的系数要除以 lim (也就是乘 lim 在模 p 下的逆元)
ps：用 NTT 比 FFT 常数小了不少呢！

\text{Part2 强力工具——多项式求逆}

在做有关多项式的题时，我们经常遇到这样的问题：
给定一个 n-1 次多项式 F(x)，求一个多项式 G(x)，使其满足：

G(x)F(x)\equiv1 \pmod{x^n}

这里模 x^n 的意义就在于，忽略次数大于等于 n 的项。

这个东西好像没法直接求，我们设一个多项式 G_1(x)，满足条件：

G_1(x)F(x)\equiv1\space (\text{mod }x^{\lceil\frac{n}{2}\rceil})

和刚才那个式子做差，可以得到：

F(x)(G(x)-G_1(x))\equiv0\space (\text{mod }x^{\lceil\frac{n}{2}\rceil})

由于 F(x) 常数项不为零，稍微化简一下，也就是

G(x)-G_1(x)\equiv0\space (\text{mod }x^{\lceil\frac{n}{2}\rceil})

将这个式子两遍同时平方：

G^2(x)-2G_1(x)G(x)+G_1^2(x)\equiv0\space (\text{mod }x^{\lceil\frac{n}{2}\rceil})

由于 G(x)-G_1(x) 的前 \lceil \frac n2 \rceil 项都是零，故多项式长度翻倍上式依然成立：

G^2(x)-2G_1(x)G(x)+G_1^2(x)\equiv0\space (\text{mod }x^n)

我们再把式子两遍同时乘 F(x)，由于G(x)F(x)\equiv1\space (\text{mod }x^n)，所以可以化简很多：

G(x)-2G_1(x)+F(x)G_1^2(x)\equiv 0\space (\text{mod }x^n)

再移项一下，就得到了最终的结果

G(x)\equiv 2G_1(x)-F(x)G_1^2(x)\space (\text{mod }x^n)

这个东西，我们可以考虑倍增或者递归地来求。
因为当 F(x) 只有常数项的时候，它的逆也就是常数项的逆元。

这个东西的时间复杂度看起来好像不太对，我们来分析一下：
倍增过程中，每次在模 x^1,x^2,x^4... 下求逆，也就是说多项式乘法每次也只用算前 1,2,4... 项，总时间复杂度就是：

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

所以实际上是没有问题的。

\text{Part3 ——多项式对数}

这个相对简单一些，我们要求一个 G(x)，满足：

G(x)\equiv \ln F(x) \pmod{x^n} $$(\ln F(x))'=\frac{F'(x)}{F(x)}$$ 再把这个东西积分一下，就变成了我们想要的式子： $$\ln F(x)=\int \frac{F'(x)}{F(x)}\text dx$$ 这样就可以直接计算了，需要用到一点微积分的基础知识。 这里就不再多赘述了。 $$\text{Part}\frac{8}{2}\text{ ——多项式除法}$$ 给一个 $n$ 次多项式 $F(x)$，$m$ 次多项式 $G(x)$，求 $n-m$ 次的 $Q(x)$，和小于 $m$ 次的 $R(x)$，满足条件： $$F(x)=G(x)Q(x)+R(x)$$ 我们先定义 $F_r(x)$ 为多项式 $F(x)$ 的**系数**翻转后的多项式，也就是设： $$F(x)=\sum\limits_{i=0}^na_ix^i$$ 则 $F_r(x) $就是： $$F_r(x)=\sum\limits_{i=0}^na_{n-i}x^i$$ 随便怎么推一下，我们就能得到： $$F_r(x)=x^nF(x^{-1})$$ 然后让我们开始正片吧！ $$F(x)=G(x)Q(x)+R(x)$$ 用 $x^{-1}$ 代换 $x$，原式仍然成立 $$F(x^{-1})=G(x^{-1})Q(x^{-1})+R(x^{-1})$$ 两遍同乘 $x^n$，式子可以变成 $$x^nF(x^{-1})=x^mG(x^{-1})x^{n-m}Q(x)+x^{n}R(x)$$ $$F_r(x)=G_r(x)Q_r(x)+x^{n}R(x)$$ 式子两边可以同时模 $x^{n-m+1}$，就能再化简为 $$F_r(x)\equiv G_r(x)Q_r(x)\space (\text{mod }x^{n-m+1})$$ 然后我们就把 $Q(x)$ 算出来了 $$ Q_r(x)\equiv F_r(x)G_r(x)^{-1}\space({\text{mod }x^{n-m+1}})$$ 算出来了 $Q(x)$，$R(x)$ 就能很快求出来 $$ R(x)=F(x)-G(x)Q(x)$$ $$\text{Part5——大毒瘤 多项式指数}$$ 这个多项式指数函数是真的可啪 QAQ 不仅难理解，还难写，我调了三天才过。。 好吧不多说了，来看题： 给一个 $n-1$ 次多项式 $F(x)$，求一个多项式 $G(x)$，满足条件： $$G(x)\equiv \text e^{F(x)} \pmod{x^n}$$ 做这个之前，我们先来想一下牛顿迭代。 牛顿迭代法可以用来求函数的零点，公式如下： $$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ 那这个和我们的题有啥关系呢？ 莫着急，答案马上揭晓。 我们考虑将原式两边同求对数，然后移项得到 $$\ln G(x) - F(x) \equiv 0\space (\text{mod }x^n)$$ $F(x)$ 是给定不变的，而 $G(x)$ 是我们要求的。 所以，我们可以将 $G(x)$ 看做自变量，$F(x)$ 看做常数进行牛顿迭代！ 关于正确性的证明，可以把它 Taylor 展开，然后发现模 $x^n$ 之后高次项都没了。由于太麻烦这里就不写了（ 于是我们就构造一个多项式 $H(x) H(G(x))=\ln G(x) - F(x)

设 G_i(x) 为第 i 次迭代的答案，然后套上牛顿迭代的公式

G_{i+1}(x) \equiv G_i(x)-\frac{H(G(x))}{H'(G(x))}\space (\text{mod } x^n)

展开，再化简成

G_{i+1}(x) \equiv G_i(x)-G_i(x)(\ln G_i(x)-F(x))\space (\text{mod } x^n) G_{i+1}(x) \equiv G_i(x)(1-\ln G_i(x)+F(x))\space (\text{mod } x^n)

看到这里，发现每次计算 G(x) 的次数都翻了一倍。
所以，如果 G_{i+1}(x) 是在模 x^n 下的答案的话，G_i(x) 就是在模 x^{\lceil\frac{n}{2}\rceil} 下的答案。

于是这个玩意就可以用类似求逆的方法，倍增地来算。
边界条件为 G(x) 次数为 0，常数项为 1。
至于时间复杂度的证明，也可以参考求逆的部分，这里就不再写一遍了。

\text{Part6——多项式快速幂}

学过对数的都知道：

\ln x^n=n \ln x

所以要计算F(x)^k，也可以用类似的办法

F(x)^k=\text e^{k\ln F(x)}

直接求对数，乘 k，再求指数就好了。

\text{Part}\sqrt{49}\text{ ——多项式开根}

由于\sqrt n=n^{\frac12}，所以可以直接用快速幂的办法来做
可是这只适用于 F(x) 常数项为 1 的情况，且时间常数较大。

如果常数项不为 1，我们就要考虑下面的方法

G(x)^2\equiv F(x)\pmod{x^n}

还是考虑牛顿迭代

H(G(x))=G(x)^2-F(x)

我们继续推式子，这部分就不做解释，指数函数的部分已经讲清楚了。

G_{i+1}(x)\equiv G_i(x)-\frac{H(G(x))}{H'(G(x))}\pmod{x^n} G_{i+1}(x)\equiv G_i(x)-\frac{G_i(x)^2-F(x)}{2G_i(x)}\pmod{x^n} G_{i+1}(x)\equiv \frac{G_i(x)^2+F(x)}{2G_i(x)}\pmod{x^n}

然后倍增求即可。
注意这里的边界条件是 G(x) 次数为 0 时，常数项为\sqrt{F(0)}
也就是解一个模意义下的二次方程，洛谷上也有模板题，具体解法就不在这里写了 qwq

\text{Part8——多项式三角函数}

一眼看过去，感觉非常不可做。。
实际上挺简单的

先来看一下大名鼎鼎的欧拉公式

\text e^{ix}=\cos x+\text i\sin x

把这个式子稍微变形一下

\text e^{-ix}=\cos x-\text i\sin x

将这两个式子相加或相减一下，得到

2\cos x=\text e^{\text ix}+\text e^{-\text ix} 2i\sin x=\text e^{\text ix}-\text e^{-\text ix}

然后我们移个项，并用F(x)代换x，就得出了结果

\cos F(x)=\frac{\text e^{\text iF(x)}+\text e^{-\text iF(x)}}{2} \sin F(x)=\frac{\text e^{\text iF(x)}-\text e^{-\text iF(x)}}{2\text i}

可是这里还有个虚数单位 \text i 呢。。这怎么取模啊QAQ
别慌，我们冷静分析一下：根据定义，虚数单位满足性质：\text i^2=-1
我们想在模意义下计算它，于是列出了一个式子

\text i^2\equiv-1\space (\text{mod }p)

这好像就是解一个二次剩余嘛！

恰好，-1 在模 998244353 意义下有二次剩余，这个方程的一个解为 86583718
也就是说，上面所有的 \text i，都用 86583718 带进去计算就好啦。

\text{Part9——多项式反三角函数}

给定一个多项式 F(x)，求一个 G(x)，满足

G(x)\equiv\sin^{-1}F(x)\space (\text{mod }x^n)

考虑将两边求导，得到

G'(x)\equiv \frac{F'(x)}{\sqrt{1-F(x)^2}}\pmod{x^n}

然后再积分回来

G(x)\equiv \int \frac{F'(x)}{\sqrt{1-F(x)^2}}\text dx\pmod{x^n}

求\tan^{-1}的方式，也差不多

H(x)\equiv\tan^{-1}F(x)\pmod{x^n} H'(x)\equiv\frac{F'(x)}{1+F(x)^2}\space (\text{mod }x^n) H(x)\equiv\int\frac{F'(x)}{1+F(x)^2}\text dx \pmod{x^n}

然后直接计算即可。

\text{Part10——多项式多点求值}

咕咕咕了很久，现在来补一下吧（

首先来证明这样一个引理：

f(x)\equiv f(a)\pmod{(x-a)}

设 f(x) = g(x)(x-a)+b，即 b \equiv f(x)\pmod{(x-a)}。
再把 a 带入上式，得到 f(a)=b，于是得证。

有了这个式子，要求 f(a)，算 f(x) \bmod (x-a) 就可以了。
虽然看起来没什么用，但别急。

根据上面的引理，还可以得到如下推论：

g(x) \equiv f(x) \bmod \left( \prod\limits_{i=1}^m(x-a_i)\right) \Rightarrow g(a_i)=f(a_i) \ (i\in [1,m])

这样一来就可以分治计算，时间复杂度
（ 这里的 n 为 \max(n,m) ）

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

注意那一堆 (x-a_i) 乘积的多项式需要分治乘预处理。
由于这个确实不好写，所以留个代码链接：Code

更新：现在已经有了根据转置原理的、时间常数更优秀的做法。在模板题的题解区已有详细说明，就不再抄一遍了。