多项式笔记（随缘更新）

基础部分

A.反演

定义A.1：称函数 \(F(i)\) 由另一函数 \(G(i)\) 表出的运算 \(f\)

\[ F(i)=f(G(i)) \]

为 \(F(i)\) 关于 \(G(i)\) 的演绎，运算 \(f^{-1}\)

\[ G(i)=f^{-1}(F(i)) \]

为 \(F(i)\) 关于 \(G(i)\) 的反演.

关于逆运算的存在性，在这里不严格证明。

计算机中主要应用的反演是离散的，上式中 \(F\) 和 \(G\) 通常以数列形式出现，\(f\) 通常会是线性算子：

\[ F_i=\sum_{j=0}^{i}A_{i,j}G_i\tag{1} \]

\[ G_i=\sum_{j=0}^{i}B_{i,j}F_i\tag{1'} \]

演绎与反演也会有积分形式（例如傅里叶变换和傅里叶反演），但并不在本节讨论的范围内.因此(1)也可以写作矩阵形式

\[ (F_1,F_2,\dots,F_n)^T=\textbf{A}(G_1,G_2,\dots,G_n)^T \]

(2)同理.

定义A.2：定义1中的 \(\textbf{A},\) \(\textbf{B}\) 分别称作演绎矩阵、反演矩阵.

由矩阵形式不难看出

性质A.1：演绎矩阵、反演矩阵互逆.

例A.1：给定一个数列 \({A_n}\) ，其前缀和与差分运算互为反演。具体地有：

\[ (S_1,S_2,\dots,S_n)^T = \left (\begin{array}{cccc}1 &0 & 0 & \dots &0&0\\1 &1 & 0 & \dots &0&0\\\vdots & \vdots & \vdots & &\vdots & \vdots \\1 &1 & 1 & \dots &1 &0\\1 &1 & 1 & \dots &1&1\\\end{array}\right)_{n}(A_1,A_2,\dots,A_n)^T \]

为前缀和，

\[ (A_1,A_2,\dots,A_n)^T = \left (\begin{array}{cccc}1 &0 & 0 & \dots &0&0\\-1 &1 & 0 & \dots &0&0\\0 & -1 & 1 & \dots &0&0\\\vdots & \vdots & \vdots & &\vdots &\vdots \\0 &0 & 0 & \dots &-1&1\\\end{array}\right)_{n}(S_1,S_2,\dots,S_n)^T \]

为差分.不难验证

\[ \left (\begin{array}{cccc}1 &0 & 0 & \dots &0&0\\1 &1 & 0 & \dots &0&0\\\vdots & \vdots & \vdots & &\vdots & \vdots \\1 &1 & 1 & \dots &1 &0\\1 &1 & 1 & \dots &1&1\\\end{array}\right)\left (\begin{array}{cccc}1 &0 & 0 & \dots &0&0\\-1 &1 & 0 & \dots &0&0\\0 & -1 & 1 & \dots &0&0\\\vdots & \vdots & \vdots & &\vdots & \vdots \\0 &0 & 0 & \dots &-1&1\\\end{array}\right) = \textbf{E}. \]

性质A.2：反演中系数可以转移.

性质A.3：反演矩阵、演绎矩阵转置后，将求和从向下至下界变为向上至上界，反演关系仍然存在.

对于性质2，可以由矩阵逆性质简单得出. 对于性质3，根据定义，演绎矩阵必然是三角阵，根据线性代数，三角阵的转置的逆等于原三角阵逆的转置.

例A.2（二项式反演）：

\[ F_n=\sum_{i=0}^{n}(-1)^i{n \choose i} G_n\iff G_n=\sum_{i=0}^{n}(-1)^i{n \choose i} F_n \]

证明：此处不用容斥证明.直接将下三角阵 \(\textbf{A}_{i,j}=(-1)^n {n \choose i}\) 平方计算便可得到需要的结果. \(\square\)

常见的形式是将 \((-1)^i\) 移至一边，即

\[ F_n=\sum_{i=0}^{n}{n \choose i} G_n\iff G_n=\sum_{i=0}^{n}(-1)^{n-i}{n \choose i} F_n \tag{2} \]

这种形式在组合数学的意义是已知使用 \(n\) 个数中某 \(i\) 个数构成特殊结构的组合方案的总合下，求出用 \(i\) 个数构成某种特殊结构的方案数.最典型的案例是错位排列数.一般来说，反演的用处就是将题给条件适当放大直到能求出解后对解进行反演.

B.生成函数基础

定义B.1：给定一个数列 \(A_i\) ，称

\[ A(x)= \sum_{i=0}^{\infty} A_ix^i\tag{3} \]

为 \(A_i\) 的生成函数或形式幂级数环.

容易看出，生成函数都是多项式，可以对其进行多项式能进行的操作：

  1. 加法，满足交换律
  2. 乘法，满足结合律、交换律
  3. 复合，满足结合律
  4. 微商，满足一元函数求导的性质
  5. 乘逆元，对 \(f^{-1}\) 作泰勒展开

由于泰勒展开的存在，如果得知一个数列的递推式，用生成函数可以求它的通项.

例B.1：求贝尔数

\[ B_{n+1}=\sum_{i=0}^{n} {n\choose i}B_i,B_0=1 \]

的通项公式.

设其指数生成函数为

\[ B(x)= \sum_{i=0}^{\infty} \frac{B_i}{i!}x^i=1+\sum_{i=0}^{\infty} \frac{B_{i+1}}{(i+1)!}x^{i+1}\tag{4} \]

其微商为

\[ B'(x)=\sum_{i=0}^{\infty} B_ix^{i+1} \]

由递推式得

\[ \frac{B_{n+1}}{n!}=\sum_{i=0}^{n}\frac{B_i}{i!}\frac{1}{(n-i)!} \]

将 \(e^x\) 的级数展开对应上式，即得

\[ B(x)=e^xB'(x) \]

这是一个一阶微分方程，变形得

\[ \frac{\mathrm dB}{B}=e^{-x}dx \]

两边积分即得

\[ B(x)=\exp(e^x+C) \]

代入边界条件即得 \(C=-1\) ,于是

\[ B(x)=\exp(e^x-1) \tag{5} \]

便是贝尔数的生成函数封闭形式.

将其第一层泰勒展开，

\[ B(x)=\frac{1}{e}(\sum_{i=0}^{\infty}\frac{1}{i!}e^{ix}) \]

第二层展开，

\[ B(x)=\frac{1}{e}(\sum_{i=0}^{\infty}\frac{1}{i!}e^{ix})\\=\frac{1}{e}(\sum_{i=0}^{\infty}\frac{1}{i!}\sum _{j=0}^{\infty}\frac{1}{j!}(ix)^j) \]

对比\((4)\)，考虑到生成函数在正数上良定义，可以交换求和顺序，用 \(n\) 替换 \(j\) 便可得出通项公式

\[ B_n=\frac{1}{e}\sum_{i=0}^{\infty}\frac{i^n}{i!}\tag{6} \]

\(\square\)

C.拉格朗日插值法

对于已知序列 \(X_i=f(x_i)\) ，考虑还原出原多项式.

首先，关于复数域上 \(n\) 个多项式根能否确定一个 \(n\) 次多项式，需要由代数基本定理给出.

定理（代数基本定理）：任何复系数一元 \(n\) 次多项式（\(n\) 至少为 1）方程在复数域上至少有一根.

该定理证明较为复杂，且与本节所述内容无太大关系，因此将其作为结论使用，证明将会留在附录给出.下面我们将得出本节最重要的成果

定理C.1（拉格朗日插值法）：数域 $ $ 上一个次数不超过 \(n\) 的多项式 \(f(x)\)，被它在 $ $ 中的 \(n+1\) 个不同元素 \(x_i\) 的函数值 \(y_i=f(x_i)\) 所唯一确定

\[ f(x)=\sum_{i=0}^{n}y_i\prod_{j=0,j\neq i}^n\frac{(x-x_j)}{(x_i-x_j)} \tag{8} \]

证明：

1）唯一性证明 考虑演绎

\[ (y_0,y_1,\dots,y_n)^T=\left (\begin{array}{cccc}1& x_0 & \dots &x_{0}^{n-1}&x_0^n\\1& x_1 & \dots &x_{1}^{n-1}&x_1^n\\ \vdots & \vdots & &\vdots &\vdots \\1& x_n & \dots &x_{n}^{n-1}&x_n^n\\\end{array}\right)(a_0,a_1,\dots,a_n)^T \tag{9} \]

为每个函数值对应系数的矩阵表示，注意到演绎矩阵 \(\textbf{V}\) 为范德蒙德矩阵，有如下引理

引理C.1：对于范德蒙德行列式，有如下结论

\[ |\textbf{V}|= \left |\begin{array}{cccc}1& x_0 & \dots &x_{0}^{n-1}&x_0^n\\1& x_1 & \dots &x_{1}^{n-1}&x_1^n\\ \vdots & \vdots & &\vdots &\vdots \\1& x_n & \dots &x_{n}^{n-1}&x_n^n\\\end{array}\right|=\prod_{0\leq i<j\leq n}(x_j-x_i) \]

证明留在附录给出.

将 \((9)\) 看作线性方程组，由于 \(x_i\) 互不相等，范德蒙德行列式不为 \(0\)，根据克拉默法则，方程有且仅有唯一解.唯一性得证.

2）必要性显然

3）充分性证明 根据克拉默法则，\((9)\) 的解为

\[ a_i=\frac{|\textbf{V}_{i}|}{|\textbf{V}|},i=0,1,\dots,n \]

其中 \(|\textbf{V}_{i}|\) 为将原矩阵次数为 \(i\) 的列替换为 \((y_0,y_1,\dots,y_n)^T\) 的行列式.因此我们有

\[ f(x)=\sum_{i=0}^n\frac{|\textbf{V}_{i}|}{|\textbf{V}|}x^i \]

我们将 \(|\textbf{V}_{i}|\) 按被替换的那列展开，即有

\[ |\textbf{V}_{i}|=\sum_{j=0}^ny_j |\textbf{V}_{ji}| \]

其中 \(|\textbf{V}_{ji}|\) 为代数余子式.因此

\[ f(x)=\sum_{i=0}^n\frac{|\textbf{V}_{i}|}{|\textbf{V}|}x^i=\sum_{i=0}^n\frac{\sum_{j=0}^ny_j |\textbf{V}_{ji}|}{|\textbf{V}|}x^i=\frac{1}{|\textbf{V}|}\sum_{j=0}^ny_j\sum_{i=0}^nx^i|\textbf{V}_{ji}| \]

其中后项关于 \(i\) 的求和事实上是将范德蒙德行列式

\[ \left |\begin{array}{cccc}1& x_0 & \dots &x_{0}^{n-1}&x_0^n\\1& x_1 & \dots &x_{1}^{n-1}&x_1^n\\ \vdots & \vdots & &\vdots &\vdots \\1& x_n & \dots &x_{n}^{n-1}&x_n^n\\\end{array}\right| \]

第 \(j + 1\) 行按照将 \(x_j^i\) 替换为 \(x^i\) 的另一范德蒙德行列式，因此由引理1

\[ \sum_{i=0}^nx^i|\textbf{V}_{ji}|=\prod_{0\leq p <q\leq n}^{p,q\neq j}(x_q-x_p)\prod_{0\leq r \leq n}^{r \neq j}(x-x_r) \]

从而

\[ f(x)=\frac{1}{|\textbf{V}|}\sum_{j=0}^ny_j\sum_{i=0}^nx^i|\textbf{V}_{ji}|=\sum_{j=0}^ny_j\frac{\prod_{1\leq p <q\leq n}^{p,q\neq j}(x_q-x_p)\prod_{1\leq r \leq n}^{r \neq j}(x-x_r)}{\prod_{1\leq p<q\leq n}(x_q-x_p)}\\=\sum_{i=0}^{n}y_i\prod_{j=0,j\neq i}^n\frac{(x-x_j)}{(x_i-x_j)} . \]

\(\square\)

代码先咕着（

D.快速多项式乘法

快速傅里叶变换算法可以在 \(O(n \log n)\) 时间内求出两个多项式的乘积.

首先阐述卷积定义以方便下文叙述.

定义D.1：将关于两个可积函数 \(f(x),g(x)\) 的生成一个新函数的运算

\[ h(x)= \int_{-\infty}^{+\infty}f(x- t)g(x)dt \tag{7} \]

称为函数的卷积运算，记作

\[ h(x)=f(x)*g(x) \]

此处的函数可以是离散函数，将积分变为求和即可.

考察两个多项式

\[ f(x)=\sum_{i=0}^{n}a_ix^i,g(x)=\sum_{i=0}^{n}b_ix^i \]

若想求出两多项式的乘积 \(h(x)=f(x)g(x)\) 的系数 \({c_i}\)，朴素的想法是直接将括号打开，一个对着另一个乘，即

\[ c_kx^k=\sum_{i=0}^{k}a_{k-i}x^{k-i}g_{i}x^i \tag{7'} \]

这事实上正是对 \(a_i,b_i\) 进行卷积操作，那么我们便可以有朴素的 \(O(n^2)\) 算法求出 \(c_i\) .

1
2
3
4
5
6
7
8
9
10
11
const int N = 200050;
int f[2 * N],g[N],c[N];

void conv(){
	for(int i = 0;i <= N;i++){
        	for(int j = 0;j <= N;j++){
            		c[i + j] += g[i] * f[i];
        	}
	}
}

这样的算法可行但效率不高，下面分两部分来介绍优化过程.

1.离散傅里叶变换（DFT）

DFT的核心思想是用函数值还原系数.

如果我们已知一个多项式的函数值，利用拉格朗日插值法可以在已知函数值和点值的情况下求出原函数的系数，下面考虑一种性质非常好的插值

定理D.1（DFT）：对于演绎

\[ X_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik} \tag{10} \]

其反演为

\[ a_k=\frac{1}{n}\sum_{i=0}^{n-1}X_i\omega_n^{-ik} \tag{10'} \]

其中 \(\omega_n\) 表示方程 \(x^n=-1\) 的单位根.我们将 \((8)\) 称为离散傅里叶变换，\((8')\) 称为逆离散傅里叶变换.

该定理在多项式上的意义是把 \(n\) 次单位根带进了多项式里，得到了 \(n\) 个值，进而反求出系数.

证明：

\[ \frac{1}{n}\sum_{i=0}^{n-1}X_i\omega_n^{-ik}\\=\frac{1}{n}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j\omega_n^{ij}\omega_n^{-ik}\\=\frac{1}{n}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j\omega_n^{i(j-k)} \]

若 \(j=k\)，显然总贡献值为 \(na_i\)；

若 \(j\neq k\)，贡献为

\[ \sum_{i=0}^{n-1}\omega_n^{i(j-k)}a_{j-k+k}=0 \]

从而推论成立.\(\square\)

这样的插值正逆极度对称，可以用相同的方法计算.

2.多项式分治

继续考虑单位根插值，我们考虑将多项式补成 \(2^n\) 次项后按奇偶分治，设

\[ FL(x)=\sum_{i=0}^{n/2-1}a_{2i}x^i,FR(x)=\sum_{i=1}^{ n/2-1}a_{2i}x^i \]

即有

\[ f(x)=FL(x^2)+xFR(x^2) \]

将单位根代入，不难推出如下分治

\[ f(\omega_n^k)=FL(\omega_n^{2k})+\omega_n^{k}FR(\omega_n^{2k}),\\f(\omega_n^{k/2+n})=FL(\omega_n^{2k})-\omega_n^kFR(\omega_n^{2k}),k\in[0,\frac{n}{2}) \tag{11} \]

这允许我们在 \(O(n\log n)\) 复杂度下求出 \(f\) 的 \(n\) 个单位根点值表示.具体地，将大的区间不断按奇偶分半递归，回溯时更新原函数值.

3.最终实现

终于可以回到多项式乘法了.

算法流程很简单：将所给多项式 \(f,g\) 分治求出单位根点值，将多项式点值对应相乘后用逆 DFT 还原系数.

代码以洛谷P3803为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
complex<double> f[5000050],g[5000050];
complex<double> tmp[5000050];
int tag[5000050];
void dft(complex<double> *ff,int n,int flg){
    if(n == 1) return;
    for(int i = 0;i < n;i++)tmp[i] = ff[i];
    for(int i = 0;i < n;i++){
        if(i & 1) ff[n / 2 + i / 2] = tmp[i];
        else ff[i / 2] = tmp[i];
    }
    complex<double> *q = ff,*p = ff + n / 2;
    dft(q,n/2,flg),dft(p,n/2,flg);
    complex<double> cur(1,0),step(cos(2 * PI/ n) ,sin(2 * PI * flg / n));
    for(int k = 0;k < n / 2;k++){
        tmp[k] = q[k] + cur * p[k];
        tmp[k + n / 2] = q[k] - cur * p[k];
        cur *= step;
    }
    for(int i = 0;i < n;i++)ff[i] = tmp[i];
}

void solve() {
    int n,m;cin>>n>>m;
    for(int i = 0;i <= n;i++){int x;cin>>x;f[i] = x;}
    for(int j = 0;j <= m;j++){int x;cin>>x;g[j] = x;}
    int t = 1;
    while(t < n + m + 2) t<<=1;
    dft(f,t,1),dft(g,t,1);
    for(int i = 0;i < t;i++) f[i] = f[i] * g[i];
    dft(f,t,-1);
    int flg = 1;
    for(int i = 0;i <= m + n;i++)cout<<int(f[i].real() / t + 0.50)<<" ";
    return;
}

这就是基础的快速多项式乘法的分治写法.