您的位置: 首页  >  IT文章  >  从零开始的多项式学习笔记 0 前言 1 ( ext{FFT}) 2 ( ext{NTT}) 3 基础题 4 多项式乘法逆 5 倍增 ( ext{FFT}) 6 分治 ( ext{FFT}) 7 多项式指对根 8 多项式除法 9 上升幂/下降幂引入 10 下降幂多项式乘法 11 多项式多点求值 12 下降幂和普通多项式的转换

从零开始的多项式学习笔记 0 前言 1 ( ext{FFT}) 2 ( ext{NTT}) 3 基础题 4 多项式乘法逆 5 倍增 ( ext{FFT}) 6 分治 ( ext{FFT}) 7 多项式指对根 8 多项式除法 9 上升幂/下降幂引入 10 下降幂多项式乘法 11 多项式多点求值 12 下降幂和普通多项式的转换

分类: IT文章 • 2022-05-26 12:14:02

膜拜多项式神 ( t{z}color{red}{houAKngyang}) 和 ( t{K}color{red}{arry5307})！

感觉最近碰到好多多项式题，但是我连最基础的 ( ext{FFT}) 都不会……

计划稍微补一下。

( ext{FFT})

1.1 准备工作

1.1.1 多项式

[A(x)=sumlimits_{i=0}^{n-1}a_ix^i ]

这是我们数学课上表达多项式的方法，也叫系数表示法。

但是，如果我们已经知道 (A(x)) 是个 (n-1) 次多项式，并且还知道了 (x) 取 (n) 个不同的值时 (A(x)) 的值，我们也能确定一个唯一的 (A(x))。

因此，我们也可以用 (n) 个点表示一个 (n-1) 次多项式，这被称作点值表示法。

多项式可以做加法。

[A(x)=sumlimits_{i=0}^{n-1}a_ix^i,B(x)=sumlimits_{i=0}^{n-1}b_ix^i ]

[C(x)=A(x)+B(x)=sumlimits_{i=0}^{n-1}(a_i+b_i)x^i ]

多项式可以做乘法。

[A(x)=sumlimits_{i=0}^{n-1}a_ix^i,B(x)=sumlimits_{i=0}^{n-1}b_ix^i ]

[C(x)=A(x) imes B(x)=sumlimits_{i=0}^{n-1}sumlimits_{j=0}^ia_jb_{i-j}x^i ]

1.1.2 复数

[i^2=-1 ]

[x=a+biquad(a,binmathbb R) ]

所有 (x) 组成的集合称之为复数集 (mathbb{C})。

一个复数对应复平面上的一个向量，其中原点为 (0)，(x) 轴为实部，(y) 轴为虚部。这个向量和 (x) 轴的夹角记为幅角 ( heta)，这个向量的长度记为复数的模长 (|x|)。

向量可以做加法。

[(a+bi)+(c+di)=(a+c)+(b+d)i ]

向量可以做乘法。

[(a+bi) imes (c+di)=(ac-bd)+(ad+bc)i ]

一个性质：如果 (x+y=z)，那么

[|z|=|x| imes|y|, heta_z= heta_x+ heta_y ]

1.1.3 单位根

[x^n=1 ]

显然这个方程在复数域存在 (n) 个互不相同的解，我们将它们按照幅角从小到大排序，记为 (omega_n^1,omega_n^2,cdots,omega_n^n)。

事实上我们有 (largeomega_n^x=(omega_n^1)^x=e^{ifrac{2kpi}{n}})。

根据上面的式子我们还知道 (largeomega_{2n}^{2x}=omega_n^x,omega_n^x=-omega_n^{frac{n}{2}+x})。

( ext{IDFT})

众所周知，由于多项式乘法的定义，在系数表示法下将两个多项式相乘是 (O(n^2)) 的。

但是，如果在点值表示法下将两个多项式相乘是 (O(n)) 的。

因此我们确定了思路：先将两个多项式搞成点值表示法，再在点值表示法下相乘，最后在倒回去。

“倒过来”的过程我们称为 ( ext{DFT})，“倒回去”的过程我们称为 ( ext{IDFT})。这两个过程优化后称为 ( ext{FFT}) 和 ( ext{IFFT})。但是实际应用中，我们一般称整个过程为 ( ext{FFT})。

( ext{DFT}) 中，我们需要找 (n) 个值代入多项式求值。

  • 我会！代入 (0,1,cdots,n-1) 算一遍就行！

这是 (O(n^2)) 的……

  • 我会！代入 (omega_n^0,omega_n^1,cdots,omega_n^{n-1}) 算一遍就行！

虽然看起来还是 (O(n^2)) 的，但是由于某些神奇的性质，我们可以优化！

我们考虑对这个多项式来点操作。下文中默认 (n) 是 (2) 的整数次幂。实际应用中可以在多项式前面补 (0)。

[A(x)=sumlimits_{i=0}^{n-1}a_ix^i ]

[=sumlimits_{i=0}^{frac{n}{2}-1}a_{2i}x^{2i}+sumlimits_{i=0}^{frac{n}{2}-1}a_{2i+1}x^{2i+1} ]

[=sumlimits_{i=0}^{frac{n}{2}-1}a_{2i}(x^2)^i+xsumlimits_{i=0}^{frac{n}{2}-1}a_{2i+1}(x^2)^i ]

我们记两个新的 (dfrac{n}{2}) 次多项式为 (A_0(x)) 和 (A_1(x))，就可以递归下去了。

然后我们在得出 (A_0(x)) 和 (A_1(x)) 之后就可以合并啦！

[A(x)=A_0(x^2)+xA_1(x^2) ]

这时，我们注意到前面单位根知识中的 (largeomega_n^i=-omega_n^{frac{n}{2}+i})，发现它们平方之后都是 (largeomega_frac{n}{2}^i)，可以一起计算这两个东西！于是我们只要让 (A_0) 和 (A_1) 告诉我们 (largeomega_frac{n}{2}^0,omega_frac{n}{2}^1,cdots,omega_frac{n}{2}^{frac{n}{2}-1}) 时多项式的值即可。

于是我们只需要 ( ext{DFT}) 一个 (n-1) 次多项式，只需要 ( ext{DFT}) (n) 个 (frac{n}{2}-1) 次多项式。而 ( ext{DFT}) 一个 (0) 次多项式显然是 (O(1)) 的，因此总复杂度是 (T(n)=nT(frac{n}{2}))，也就是 (O(nlog n)) 的！

于是你已经会 ( ext{DFT}) 了。

( ext{IDFT}) 的证明比较复杂，由于我们是实用主义者，我们只要再来一次类似 ( ext{DFT}) 的操作，但这次代入 (-omega_n^i)，而且在结束后把每一项除以 (n)，就是原来的多项式了。

于是你也会 ( ext{IDFT}) 了，可以递归实现 ( ext{FFT}) 了。

1.3 常数优化

考虑我们 ( ext{DFT}) 的时候系数的下标是怎么分布的。

[{0,1,2,3,4,5,6,7} ]

[{color{red}{0,2,4,6}color{black}{,}color{blue}{1,3,5,7}color{black}} ]

[{color{red}{0,4}color{black},color{blue}{2,6}color{black},color{red}{1,5}color{black},color{blue}3,7color{black}} ]

[{color{red}{0}color{black},color{blue}{4}color{black},color{red}{2}color{black},color{blue}6color{black},color{red}{1}color{black},color{blue}{5}color{black},color{red}{3}color{black},color{blue}7color{black}} ]

经过观察可以发现，(x) 最终的位置是将 (x) 的二进制位前后翻转的数字！

那么，我们就可以舍弃这种低效的做法，直接一步到位转好系数，直接自底向上合并！

这样减少了很多不必要的内存访问，同时也会更加好写。

对于这一步，你当然可以一位一位整，但还是太慢了，有一种很方便的实现方法。

最开始往数组里放两个数 (a_1=0,a_2=frac{n}{2})。

然后依次翻转次高，次次高，次次次高的位，将新数接在原数后面，直到完成数组。

( ext{NTT})

2.1 原根

( t{z}color{red}{houAKngyang}) 说在大多数情况下我们只需要找一个原根，所以并不需要做原根模板题。

注意到在 ( ext{FFT}) 中我们用了单位根来 ( ext{DFT})，但是单位根需要用到复数和浮点运算，不仅效率不高，还会有精度损失。原根就可以拿来代替单位根。

列出我们用到的单位根的性质：

  1. (largeomega_n^0,omega_n^1,cdots,omega_n^{n-1}) 两两不同。
  2. (largeomega_{2n}^{2m}=omega_{n}^{m})。
  3. (largeomega_{n}^{m}=-omega_{n}^{frac{n}{2}+m})。
  4. (largesumlimits_{i=0}^{n-1}omega_n^i=0)

然后你并不需要知道原根是什么，你只需要知道如果正整数 (g) 是质数 (p) 的原根，那么 (g^t\%p) 就可以代替 (omega_n^1) 了，其中 (t=lfloorfrac{p-1}{n} floor)。

啊？您问我说为什么？我也不知道，爬。

2.2 没了

啊？剩下的和 ( ext{FFT}) 一模一样，回上一章复习，请。

( ext{NTT}) 模数

并不是所有质数都能拿来 ( ext{NTT})，只有部分可以。

最常见的是 (1004535809) 和 (998244353)，原根都是 (3)。

其余 ( ext{NTT}) 模数请百度“NTT模数表”。

( ext{NTT})

于是我们可以想到把多项式乘起来的真实值算出来然后最后取模，但会爆 long long。

于是我们考虑大力用三个 ( ext{NTT}) 算出这个值在三个模数下的值，最后 ( ext{CRT}) 合并即可。

感谢教练 ( t{d}color{red}{evinwang}) 给的博客资源，拆系数 ( ext{FFT}) 在写了（（（

( ext{FFT})

注意到系数太大会爆 double 的精度，( ext{NTT}) 在模意义下可以用 ( ext{CRT})，( ext{FFT}) 就不太行了，只能把系数拆掉。

由于系数最大是 (10^9)，我们开个根号为 (32768)，记为 (M)，则

[A(x)=sum_{i=0}^{n-1}a_ix^i=sum_{i=0}^{n-1}(p_iM+q_i)x^i=Msum_{i=0}^{n-1}p_ix^i+sum_{i=0}^{n-1}q_ix^i=MA_0(x)+A_1(x) ]

[(MA_0(x)+A_1(x))(MB_0(x)+B_1(x))=M^2A_0(x)B_0(x)+M(A_0(x)B_1(x)+A_1(x)B_0(x))+A_1(x)+B_1(x) ]

因此我们可以通过 (7) 次 ( ext{FFT}) 来完成计算。

注意：由于要保留约 (15) 位数字，请使用 long double。

3 基础题

学会 ( ext{FFT}) 和 ( ext{NTT}) 之后就可以写一点简单的多项式题喽！

目前打算跟着 ( t{K}color{red}{arry5307}) 的题单刷。

3.1 [ZJOI2014]力

因为是第一题所以这个菜鸡看了题解，然后就被 ( t{z}color{red}{houAKngyang}) d了！

多项式题的关键是将要求的东西变成卷积形式，即 (largesumlimits_{i=0}^na_ib_{n-i})。

不难发现后面的式子和前面是反着的，而前面这个已经是卷积形式了（(a_i=q_i,b_i=dfrac{1}{i^2})），然后就两遍 ( ext{FFT}) 切了。

草这个题也太板了吧……

3.2 [AH2017/HNOI2017]礼物

这个题没有这么板了，于是这个菜鸡又看了题解，然后被 ( t{z}color{red}{houAKngyang}) 强行制止了……

先考虑两个环都确定下来了怎么做。

战术拆开贡献，得到 (x_i^2+y_i^2-2x_iy_i)，所以我们要求的是 (largemax{sumlimits_{i=1}^nx_iy_i})。

注意到卷积形式是 (largesumlimits_{i=0}^na_ib_{n-i})，这相当于一个翻转操作，我们可以先翻过来再翻回去。

现在的问题是如何重排 (b) 使得 (largesumlimits_{i=0}^na_ib_{n-i}) 最小，然后你发现根本不需要重排，把 (b) 倍长之后卷一下，把中间几项加起来就行了。

这样的复杂度目测是 (nmlog n)，不太行啊……

哦我们把 (x_i) 改成 (x_i+d_i)，就能得到 ((x_i-y_i+d_i)^2=x_i^2+y_i^2-2x_iy_i+d_i^2+2(x_i-y_i)d_i) 了，卷一下再直接枚举 (d) 就行。

诶这是我自己切的第一个 poly 题诶！

不过被 ( t{z}color{red}{houAKngyang}) 怒斥三岁小孩有手就行了/kk

3.3 差分和前缀和

还是根据套路构造卷积。先考虑做一次前缀和。

我们会发现 (c_i=sumlimits_{j=0}^ia_j)，根据卷积形式我们还要构造一个 (b_j)。然后发现 (b_j) 好像全部是 (1) 就满足条件。

所以设 (B(x)=x^{n-1}+x^{n-2}+cdots+1)，我们要求的就是 (A(x) imes B(x)^k) 的后 (n) 项。

啊？我不会多项式快速幂，并且 (k=10^{2333}) 快速幂好像也不太行，考虑用数学方法计算 (B(x)^k)。

哦这个不是随便算吗，第 (i) 项系数就是 (dbinom{k+i-1}{i})，注意到要对 (1004535809) 取模边读入边模就好了。

好像并不难的样子！

再考虑做一次差分。我们会发现 (c_i=a_i-a_{i-1})，虽然这和卷积都没啥关系了，但是我们还是把 (a) 搞成以 (1) 为下标的，构造一个 (B(x)=1-x)，然后再算一下 (B(x)^k)，根据二项式系数可以得到第 (i) 项系数就是 ((-1)^idbinom{k}{i})。

好像也不难的样子！

又被 ( t{z}color{red}{houAKngyang}) 怒斥这么简单的题都不能不看题解自己实现了

3.4 【CSGRound2】开拓者的卓识

推了半天没推出来

一开始想按照上一题的套路来做，发现自己还是 ( ext{Naive}) 了。

这题我们不妨跳过错综复杂的递归，直接考虑每个数对总答案贡献几次。

考虑一个数如何对总答案进行贡献，其实就是被 (k) 重区间包着最后送给总答案。例如 (a_3) 就可以在 (sum_{1,3,4},sum_{2,1,4},sum_{3,1,4}) 中给 (sum_{3,1,4}) 贡献。注意到区间的左半部分和右半部分互不相干，我们再套路地搞一个式子 (c_i=sumlimits_{j=1}^ia_jf_jf_{i-j+1})，于是现在只要求出 (f_j) 怎么算就好了。

我们考虑 (f_j) 是啥。稍微想了一下，事实上就是在 ([1,j]) 选 (k-1) 个数（最后一个必须是 (1)），可以重复。这样有多少种方法呢？插板一算，(dbinom{j+k-1}{j-1}) 种，然后这题又做完了。

3.5 Super Poker

我使用了生成函数切掉这题，请移步生成函数学习笔记（

3.6 Red-White Fence

注意到周长其实就是红板长度加上选的板子的数量。

于是当我们确定了红板长度 (L) 和周长 (C) 之后，我们需要取出 (frac{C}{2}-L-1) 块白板。

然后很恶心的是虽然板子不能一样长，但是可以在红板两侧各来一块相同长度的白板。

于是我们发现一种颜色的白板超过两条和两条是等价的。

然后我们考虑两种特殊情况：

  • 所有白板都只有一条。

这种情况下，我们可以先选 (j) 条，然后分别考虑每条放左边还是右边。

如果从 (i) 种白板中选出 (j) 条，那么有 (2^jinom{i}{j}) 种方案。

  • 所有白板都有两条。

我们让第一条代表放在左边，第二条代表放在右边。

那么一种方案和选 (j) 条板子是一一对应的。

那么如果从 (i) 种白板种选出 (j) 条，那么有 (inom{2i}{j}) 种方案。

然后我们发现选出 (i) 条白板的过程可以拆解成选出 (j) 条只有一条的白板和 (i-j) 条有两条的白板。

于是我们只需要把两部分拆开即可，先算出选出 (j) 条只有一条的白板和有两条的白板的方案数，然后卷积即可。

注意到白板的长度要小于红板，所以要对于每块红版单独 ( ext{NTT}) 一次。

4 多项式乘法逆

4.1 介绍

数有逆元，多项式也有。

数的逆元乘起来等于 (1)，多项式和它的逆乘起来也等于 (1)。

但是你发现两个多项式乘起来次数更高，因此这里的逆元是在模 (x^n) 意义下的，(n) 为多项式最高次数加 (1)，也就是把多出来的位数砍掉。

比如 (A(x)=x-1) 的逆元就是 (B(x)=x+1)，因为它们乘起来等于 (x^2+1equiv 1pmod{x^n})。

4.2 算法

我们仍然考虑递归求解。假设我们已经知道了 (B_0) 使得

[A(x) imes B_0(x)equiv 1pmod{x^frac{n}{2}} ]

要求 (B) 使得

[A(x) imes B(x)equiv 1pmod{x^{n}} ]

[B_0(x)-B(x)equiv 0pmod{x^frac{n}{2}} ]

两边平方。

[B_0(x)^2+B(x)^2-2B_0(x)B(x)equiv 0pmod{x^n} ]

同乘 (A(x))。

[A(x)B_0(x)^2+B(x)-2B_0(x)equiv 0pmod{x^n} ]

[B(x)equiv2B_0(x)-A(x)B_0(x)^2pmod{x^n} ]

然后暴力算就好了。

Note:注意到虽然 ( ext{NTT}) 求到了 (2n) 次项，但是我们依旧只取准确的前 (n) 次项。

4.3 任意模数多项式乘法逆

这个题目不讲武德，卡常（恼

好啊，(18) 次 ( ext{NTT}) 换成 (15) 次就过了，良心出题人！

( ext{FFT})

5.1 介绍

( ext{FFT}) 在倍增上的小应用。

如果一个多项式可以通过某种方式递推，但是要求 (10^9) 项的系数，我们就可以尝试倍增 ( ext{FFT})。

倍增 ( ext{FFT}) 的关键在于将第 (i) 项转移到第 (i+1) 和第 (2i) 项。有时候还需要处理第 (i-1,i-2) 项。

5.2 PolandBall and Many Other Balls

大家千万不要被倍增 ( ext{FFT}) 吓到了，事实上倍增 ( ext{FFT}) 的主要点还是在倍增上，( ext{FFT}) 只起辅助作用。

如果 (n,kleq 1000)，相信大家都会做吧。

我们设 (f_{i,j}) 为在前 (i) 个数选 (j) 组的方案数，那么 (f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1})。

然后数据范围变大了，这个 dp 就过不去了，我们考虑是否有更高明的方法。

由于这是个 ( ext{FFT}) 题，脑洞大开，发现了一种神奇的方法：

注意到两段长度为 (j) 和 (i-j) 的序列合起来，长度就是 (i) 的。于是我们可以将长度为 (i) 的序列拆解成长度为 (j) 和 (i-j) 的序列。

但是存在一个例外情况：那就是 (j) 和 (j+1) 组成一组，这种情况我们则可以拆解成长度为 (j-1) 和 (i-j-1) 的序列，即当作一个长度为 (i-2) 的序列。

于是我们得到了 (f_{x,i}=sumlimits_{j=0}^if_{y,j}f_{z,i-j}+sumlimits_{j=0}^if_{y-1,j}f_{z-1,i-j})，而只需要满足 (x=y+z)，(y) 和 (z) 可以任选。

然后我们发现我们已经搞出了卷积式 (c_i=sumlimits_{j=0}^ia_jb_{i-j}) 的形式，于是就可以整一个多项式了。

设 (F_n(x)=sumlimits_{i=0}^k f_{n,k}x^i)。那么我们就可以写出一些式子。

首先，最基础的 (1) 式：(F_n(x)=(x+1)F_{n-1}(x)+xF_{n-2}(x))

然后，新的 (2) 式：(F_n(x)=F_m(x)F_{n-m}(x)+xF_{m-1}(x)F_{n-m-1}(x))

然后就到了喜闻乐见的倍增 ( ext{FFT}) 时间：接下来我们考虑怎么通过 (F_{n}(x)) 求出 (F_{2n}(x))。

首先根据 (2) 式可以知道 (F_{2n}(x)=F_n^2(x)+xF_{n-1}^2(x))，于是我们考虑如何维护 (F_{2n-1}(x))。

然后再用 (2) 式可以知道 (F_{2n-1}(x)=F_n(x)F_{n-1}(x)+xF_{n-1}(x)F_{n-2}(x))，于是我们考虑如何维护 (F_{2n-2}(x))。

最后再用 (2) 式可以知道 (F_{2n-2}(x)=F_{2(n-1)}(x)=F_{n-1}^2(x)+xF_{n-2}^2(x))，于是这道题就做完了。

总结一下倍增板子：

int t=highbit(n)>>1;
//set F(0)
for(; t>=1; t>>=1)
{
	mul();
	if(n&t) add();
}

其中 (f1) 将 (x) 变成 (2x)，(f2) 将 (x) 变成 (x+1)。

5.3 Transforming Sequence

这个 (nleq 10^{18}) 是啥啊……这不明显 (nleq k) 吗？？？

考虑每个数每一位的情况：之前选过的位可选可不选，之前没选过的位至少要选一个。

于是列个 dp 式子。设 (f_{n,i}) 为前 (n) 个数的或中有 (i) 个 (1) 的方案数，

[f_{n,i}=sum_{j=0}^{i-1}f_{n-1,j}2^jinom{i}{j} ]

我们已经看到卷积了，开始化简！

[f_{n,i}=sum_{j=0}^{i-1}f_{n-1,j}2^jinom{i}{j} ]

[=sum_{j=0}^{i-1}f_{n-1,j}2^jfrac{i!}{(i-j)!j!} ]

[=i!sum_{j=0}^{i-1}(f_{n-1,j}2^jfrac{1}{j!})frac{1}{(i-j)!} ]

于是我们用 ( ext{FFT}) 计算可以做到 (O(nklog k))。

然后我们考虑优化。如果我们把序列前后两部分分开，我们发现，后面的数中，前面的位可以随便选。

所以我们得到了另一个式子：令 (n=a+b)，

[f_{n,i}=sum_{j=0}^if_{a,j}f_{b,i-j}2^{bj}inom{i}{j} ]

[=sum_{j=0}^if_{a,j}f_{b,i-j}2^{bj}frac{i!}{j!(i-j)!} ]

这个东西一脸可以倍增的样子，我们设 (m=frac{n}{2})

[f_{n,i}=i!sum_{j=0}^if_{m,j}frac{1}{j!}f_{m,i-j}frac{1}{(i-j)!}2^{mj} ]

然后就做完啦！

( ext{FFT})

6.1 介绍

考虑有这么个东西。

[f_i=sum_{j=0}^{i-1}f_jg_{i-j} ]

告诉你 (g) 数组，求 (f) 数组。

然后你发现这个东西非常的卷积形式，但是又不能直接卷积，因为后面的项需要前面的信息。

然后我们考虑将答案拆成几部分。

比如我们将 (f(7)) 的贡献二进制拆分成 ([0,3]+[4,5]+[6,6])。

然后我们就可以分治了。在区间 ([l,r]) 中，我们只需要做这些事情：

  1. 如果 (l=r) 返回。
  2. 递归左区间。
  3. 处理左区间对右区间的贡献。
  4. 递归右区间。

这样你会发现拆出来的每一段都被处理过，问题就完美解决了。

啊？您说为什么？自己手模一遍就好了。

现在我们考虑左区间对右区间的贡献。

[f_i=sum_{j=l}^{r}f_jg_{i-j} ]

与之不同的是这个时候我们已经知道所有的 (f_j) 了，可以直接卷了。

注意到 (f) 的前几项都是空的，我们可以平移一下再卷，减少项数。

因此分析时间复杂度为 (T(n)=2T(frac{n}{2})+nlog n)，我不会主定理但是这看起来是 (O(nlog^2n)) 的。

7 多项式指对根

7.0 多项式求导积分

很多多项式指对幂都依赖于求导积分这一操作。

由于它们是可逆的，所以我们可以放心操作。

求导：((x^a)'=ax^{i-1})。

积分：(int x^adx=frac{1}{a+1}x^{a+1})

然后这些显然都是 (O(n)) 的。

(ln)

[G(x)=ln(F(x)) ]

[G'(x)=ln'(F(x))F'(x) ]

[G'(x)=frac{F'(x)}{F(x)} ]

[G(x)=intfrac{F'(x)}{F(x)}dx ]

由于我们只关心多项式模 (x^n) 的值，所以不需要多项式除法，直接多项式求逆即可。

(exp)

比 (ln) 难亿点。

7.2.1 泰勒展开

请 自 行 查 阅 知 乎 第 一 篇 回 答。

由于某些不可告人的原因，不细讲。

7.2.2 牛顿迭代

假如我们要求函数 (F(x)) 使 (G(F(x))equiv0pmod {x^{n}})。

假设我们已经知道了 (G(F_0(x))equiv0pmod {x^{frac{n}{2}}})

然后我们欢乐在 (F_0(x)) 处泰勒展开：(G(F(x))=sumlimits_{i=0}^inftydfrac{G^i(F_0(x))}{i!}(F(x)-F_0(x))^i)

然后由于我们对 (x^n) 取模，因此只需要取 (i=0,1) 的情况即可。

[G(F(x))=G(F_0(x))+G'(F_0(x))(F(x)-F_0(x)) ]

[0equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))pmod {x^n} ]

[F(x)equiv F_0(x)-frac{G(F_0(x))}{G'(F_0(x))}pmod{x^n} ]

7.2.3 正片

[e^{A(x)}=B(x) ]

[A(x)=ln B(x) ]

[f(B(x))=ln B(x)-A(x)=0 ]

于是我们就可以求零点了，我们直接让 (A(x)) 成为一个常数。

[B(x)=B_0(x)-frac{f(B_0(x))}{f'(B_0(x))} ]

[B(x)=B_0(x)-frac{ln B_0(x)-A(x)}{frac{1}{B_0(x)}} ]

[B(x)=B_0(x)(1-ln B_0(x)+A(x)) ]

众所周知我们可以求一个多项式的 (ln)，然后这个就做完了。

显然模 (x^1) 意义下 (ln B(x)=0)，那么让 (B(x)=1) 即可。

7.3 多项式开根

同样使用牛顿迭代。

[B^2(x)=A(x) ]

[f(B(x))=B^2(x)-A(x)=0 ]

于是我们就可以求零点了，我们直接让 (A(x)) 成为一个常数。

[B(x)equiv B_0(x)-frac{f(B_0(x))}{f'(B_0(x))}pmod{x^n} ]

[B(x)equiv B_0(x)-frac{B_0^2(x)-A(x)}{2B_0(x)}pmod {x^n} ]

[B(x)equiv frac{B_0^2(x)+A(x)}{2B_0(x)}pmod {x^n} ]

众所周知我们可以求一个多项式的逆，然后这个就做完了。

8 多项式除法

[frac{A(x)}{B(x)}=A(x)+frac{1}{B(x)} ]

这个大家都知道吧。

但是这个多项式除法可以求商和余数，是不是很神奇（

首先，我们考虑一个多项式系数翻转的代数意义是什么。

啊这当然很简单，一个 (n) 次多项式翻转相当于 (x^nF(frac{1}{x}))。

有了这个能干什么用呢？我们开始推柿子。

下文 (F(x)) 是 (n) 次的，(G(x)) 是 (m) 次的。

[F(x)=G(x)Q(x)+R(x) ]

[F(frac{1}{x})=G(frac{1}{x})Q(frac{1}{x})+R(frac{1}{x}) ]

我们定义 (x^nF(frac{1}{x})=F_0(x))。

[x^nF(frac{1}{x})=x^nG(frac{1}{x})Q(frac{1}{x})+x^nR(frac{1}{x}) ]

[x^nF(frac{1}{x})=x^mG(frac{1}{x})x^{n-m}Q(frac{1}{x})+x^{n-m+1}x^{m-1}R(frac{1}{x}) ]

[F_0(x)=G_0(x)Q_0(x)+x^{n-m+1}R_0(x) ]

如果我们模 (x^{n-m+1}) 就可以得到 (F_0(x)equiv G_0(x)Q_0(x)pmod {x^{n-m+1}})

因为 (Q_0) 是个 (n-m) 次多项式，因此我们可以直接得到 (Q_0)，然后求出 (Q) 和 (R)。

然后就做完了。

9 上升幂/下降幂引入

9.1 定义

(x^{underline n}) 是 (x) 的 (n) 次下降幂。

(x^{overline n}) 是 (x) 的 (n) 次上升幂。

[x^{underline n}=x(x-1)(x-2)cdots(x-n+1) ]

[x^{overline n}=x(x+1)(x+2)cdots(x+n+1) ]

9.2 性质

众所周知对于普通多项式 (F(x)) 我们可以微分。

[Df(x)=limlimits_{h o 0}frac{f(x+h)-f(x)}{h} ]

[D(x^n)=nx^{n-1} ]

事实上下降幂也有这个优美的性质，但是不是微分，而是差分。

[Delta f(x)=f(x+1)-f(x) ]

[Delta(x^{underline n})=nx^{underline{n-1}} ]

众所周知 OI 里很多函数可能是离散的，所以差分有时可以解决微分不能解决的东西。

另外，下降幂和普通多项式还有很多类似的性质：

[int!x^k=frac{x^{k+1}}{k+1} ]

[sum_{i=0}^{n-1}!x^{underline k}=frac{n^{underline{k+1}}}{k+1} ]

甚至 (k=-1) 的特例也是一样的：

[int!x^{-1}=ln x ]

[sum_{i=0}^{n-1}frac{1}{i+1}=sum_{i=1}^{n}frac{1}{i} ]

我们得到了中华级数调和级数，和 (ln) 也有联系。

10 下降幂多项式乘法

众所周知普通多项式乘法需要先转点值，那么我们也尝试转一下点值。

这里的点值显然不能取 (x=omega_n^0,omega_n^1,cdots,omega_n^{n-1})。

由于下降幂多项式可以差分，我们考虑 (x=0,1,2,cdots,n-1)。

我们考虑搞这个点值序列的 ( ext{EGF})。

[F^#(x)=sum_{i=0}^inftyfrac{F(i)}{i!}x^i ]

看起来这玩意很难搞，我们先考虑 (F(x)=x^{underline n}) 的情况。

[sum_{i=0}^inftyfrac{i^{underline n}}{i!}x^i=sum_{i=0}^infty[igeq n]frac{1}{(i-n)!}x^i ]

[=x^nsum_{i=0}^inftyfrac{1}{i!}x=x^ne^x ]

于是我们可以对于每一项分别计算：

[F^#(x)=sum_{i=0}^inftyfrac{F(i)}{i!}x^i ]

[=e^xsum_{i=0}^infty F[i]x^i ]

然后我们就可以得到 ( ext{EGF}) 了。我们 ( ext{EGF}) 转 ( ext{OGF}) 再转 ( ext{EGF}) 就得到了两个多项式乘起来的 ( ext{EGF})，最后乘 (e^{-x}) 即可转换回乘积的下降幂多项式。

11 多项式多点求值

考虑一个多项式 (G(x)=(x-x_0))。

我们用 (F(x)) 去除 (G(x))，得到 (F(x)=G(x)Q(x)+R(x))。

注意到 (G(x)) 只有一次，所以 (R(x)) 是 (0) 次的。

如果 (x=x_0)，那么上式的 (F(x_0)=G(x_0)Q(x_0)+R(x_0))。

[ecause G(x_0)=x_0-x_0=0 ]

[ herefore F(x_0)=R(x_0) ]

于是我们只需要知道

[F(x)mod(x-x_i) (i=1,2,cdots,m) ]

就做完了。

考虑怎么快速求上面的式子，我们考虑分治。

我们先求出多项式 (prodlimits_{i=1}^klimits(x-x_i)) 和 (prodlimits_{k+1}^m(x-x_i))，然后让 (F(x)) 对它们取模，得到 (F_0(x)) 和 (F_1(x))。

然后我们将 (F_0(x)) 和 (F_1(x)) 再递归下去，分别求出 (iin[1,k]) 和 (iin[k+1,m]) 时的值。

注意到 (prodlimits_{i=1}^klimits(x-x_i)) 和 (prodlimits_{k+1}^m(x-x_i)) 也可以预处理，那么我们就可以做了。

分析一下时间复杂度：(T(n)=2T(frac{n}{2})+nlog n=O(nlog^2 n))

12 下降幂和普通多项式的转换

12.1 普通多项式转下降幂多项式

12.1.1 暴力做法

众所周知我们知道下降幂多项式点值的 ( ext{EGF}) 就可以求出下降幂了。

于是一个暴力的做法是上多项式多点求值暴力求出 (n) 个位置的值。

12.1.2 周队算法

这是 ( t zcolor{red} t houAKngyang) 发明的第一个算法！

该名称已经经过 ( t zcolor{red} t houAKngyang) 确认。

  • 前置知识：
  1. (O(nlog n)) 多项式除法/取模
  2. (O(nlog n)) 下降幂/上升幂单项式转普通多项式（第一类斯特林数·行）
  3. （非必须）分治 ( ext{FFT})

首先这个方法不需要难写常数大的多项式多点求值，但是本质还是分治。

注意到我们可以把式子拆开。

[G(x)=sum_{i=0}^mg_ix^{underline{i}}+sum_{i=m}^ng_ix^{underline{i}} ]

[=sum_{i=0}^{m}g_ix^{underline{i}}+x^{underline{m+1}}sum_{i=m+1}^ng_i(x-m)^{underline{i-m-1}} ]

[=G_0(x)+x^{underline{m+1}}G_1(x-m) ]

我们对 (x^{underline{m+1}}) 取模，然后也得到了 (F(x)=F_0(x)+x^{underline{m+1}}F_1(x))。

然后我们递归继续这个过程。注意继续递归时式子可能是 (G(x-m))。

时间复杂度 (T(n)=2T(frac{n}{2})+nlog n=Theta(nlog^2n))。

相关推荐