多项式全家桶学习笔记（进阶）

好的继续一点一点啃吧

Todo List
  • “鸽了”的实现
  • 多项式复合
  • 多项式复合逆
  • 快速沃尔什变换
  • 快速莫比乌斯变换
  • 常系数线性递推
  • 常系数齐次线性递推
  • 一大堆东西

目录

一.数学前置

1.1 二项式反演

[f(n)=sum_{i=0}^{n}(-1)^iinom{n}{i}g(i) ]

等价于

[g(n)=sum_{i=0}^{n}(-1)^{n-i}inom{n}{i}f(i) ]

Proof

证明一：参考

显然只要证明前推后即可。

考虑二式的右边。

[egin{aligned} sum_{i=0}^{n}(-1)^{n-i}inom{n}{i}f(i)&=sum_{i=0}^{n}(-1)^{n-i}inom{n}{i}sum_{j=0}^{i}inom{i}{j}g(j)\&=sum_{i=0}^{n}sum_{j=0}^{i}(-1)^{n-i}inom{n}{i}inom{i}{j}g(j)\&=sum_{j=0}^{n}sum_{i=j}^{n}(-1)^{n-i}inom{n}{i}inom{i}{j}g(j)\&=sum_{j=0}^{n}sum_{i=j}^{n}(-1)^{n-i}inom{n}{j}inom{n-j}{i-j}g(j)\&=sum_{j=0}^{n}inom{n}{j}g(j)sum_{i=j}^{n}(-1)^{n-i}inom{n-j}{i-j}\&=sum_{j=0}^{n}inom{n}{j}g(j)[j=n]\&=g(j) end{aligned} ]

得证。

证明二：（by 神虎）

啥也不说，%就完了。

注意到前面等价于 (F(x)=G(x-1))，后面等价于 (G(x)=F(x+1))，于是得证。

1.2 拉格朗日反演

[G(F(x))=x ]

则

[[x^n]F(x)=frac{1}{n}[x^{-1}](frac{1}{G(x)})^n ]

Proof

证明：

看不懂神仙EI的做法，只能看别人的做法了.jpg

设

[F(x)=sum_{i}a_ix^i ]

所以

[egin{aligned} sum_{i}a_iG^i(x)&=x\ sum_{i}a_iiG^{i-1}(x)G'(x)&=1\ sum_{i}a_iiG^{i-n-1}G'(x)&=frac{1}{G^n(x)}\ [x^{-1}]sum_{i}a_iiG^{i-n-1}G'(x)&=[x^{-1}]frac{1}{G^n(x)} end{aligned} ]

而当(i eq n)时，显然对左式没有贡献，可得

[[x^{-1}]a_nnG^{-1}G'(x)=[x^{-1}]frac{1}{G^n(x)} ]

注意到

[egin{aligned} [x^{-1}]G^{-1}(x)G'(x)&=[x^{-1}]frac{a_1+2a_2x+3a_3x^2+cdots}{a_1x+a_2x^2+cdots}\&=[x^{-1}](frac{a_1+2a_2x+3a_3x^2+cdots}{a_1x} imes frac{1}{1+frac{a_2}{a_1}x+frac{a_3}{a_1}x^2+cdots})\&=1 end{aligned} ]

所以

[a_nn=[x^{-1}]frac{1}{G^n(x)} ]

即

[[x^n]F(x)=a_n=frac{1}{n}[x^{-1}]frac{1}{G^n(x)} ]

证毕。

1.3 单位根反演

设(omega)表示(n)次本原单位根

则我们有

[[n|k]=frac{1}{n}sum_{i=0}^{n-1}omega^{ik} ]

Proof

证明：

当 (n|k) 时，有 (omega^{ik}=1)，显然成立！

当 (n mid k) 时，有

[sum_{i=0}^{n-1}omega^{ik}=frac{1-omega^{nk}}{1-omega^k}=0 ]

得证！

1.4 斯特林数

先给出斯特林数的定义：

第一类斯特林数 (egin{bmatrix}n\kend{bmatrix}) 表示将 (n) 个两两不同的元素，划分为 (k) 个非空圆排列的方案数。

第二类斯特林数 (egin{Bmatrix}n\kend{Bmatrix}) 表示将 (n) 个两两不同的元素，划分为 (k) 个非空子集的方案数。

有如下递推式：

[egin{bmatrix}n\kend{bmatrix}=egin{bmatrix}n-1\k-1end{bmatrix}+(n-1)egin{bmatrix}n-1\kend{bmatrix} ]

[egin{Bmatrix}n\kend{Bmatrix}=egin{Bmatrix}n-1\k-1end{Bmatrix}+kegin{Bmatrix}n-1\kend{Bmatrix} ]

有用的式子

[n^m=sum_{k=0}^{m}egin{Bmatrix}m\kend{Bmatrix}inom{n}{k}k!=sum_{k=0}^{m}egin{Bmatrix}m\kend{Bmatrix}n^underline{k} ]

[x^overline{k}=sum_{k=0}^{n}egin{bmatrix}n\kend{bmatrix}x^k ]

斯特林反演

[f(n)=sum_{k=0}^{n}egin{Bmatrix}n\kend{Bmatrix}g(k) ]

等价于

[g(n)=sum_{k=0}^{n}(-1)^{n-k}egin{bmatrix}n\kend{bmatrix}f(k) ]

通项公式

[egin{Bmatrix}n\kend{Bmatrix}=sum_{i=0}^{k}frac{i^n(-1)^{k-i}}{i!(k-i)!} ]

这个可以用二项式反演或者直接组合意义容斥来证

二.进阶多项式算法

2.1 Bluestein's Algorithm

orz myy！

注：原论文似乎有点问题，如果发现这里也有问题欢迎指出。

模板

( ext{Bluestein's Algorithm}) 支持任意长度 ( ext{CZT})，即给出多项式 (B(x))，计算

[a_i=B(c^i)=sum_{k=0}^{n-1}c^{mk}b_k ]

考虑如何将其化为普通卷积的形式。

下面我们用一种膜法，注意到这么一个恒等式：

[mk=frac{-(m-k)^2+m^2+k^2}{2} ]

正确性显然。

通常称为 ( ext{Bluestein}) 的第一个拆乘积的方法。

代入上面的式子：

[egin{aligned}a_m&=sum_{k=0}^{n-1}c^{mk}b_k\&=sum_{k=0}^{n-1}c^{frac{-(m-k)^2+m^2+k^2}{2}}b_k\&=c^{frac{m^2}{2}}sum_{k=0}^{n-1}c^{-frac{(m-k)^2}{2}}c^{frac{k^2}{2}}b_kend{aligned} ]

发现是个卷积，于是直接 NTT 就好了……

吗？

我们发现指数不是整数，这意味着只有在 (c) 有二次剩余的时候才可以，但是通常不存在。

有没有不依赖二次剩余的方法呢？

我们发现了另一个式子：

[mk=inom{m+k}{2}-inom{m}{2}-inom{k}{2} ]

于是

[egin{aligned}a_m&=sum_{k=0}^{n-1}c^{mk}b_k\&=sum_{k=0}^{n-1}c^{inom{m+k}{2}-inom{m}{2}-inom{k}{2}}b_k\&=c^{-inom{m}{2}}sum_{k=0}^{n-1}c^{inom{m+k}{2}}omega^{-inom{k}{2}}b_kend{aligned} ]

这就是一个卷积的形式了，直接 NTT 即可。

复杂度 (O(nlog n))。

Code 
vec CZT(vec f,int len,int c,int m){
	vec A(len),B(len+m),g(m);
	for(int i=0;i<len;i++)A[i]=1LL*qpow(c,P-1-F(i))*f[i]%P;
	for(int i=0;i<len+m;i++)B[i]=qpow(c,F(i));
	reverse(A.begin(),A.end());
	A=mul(A,B,len*2+m);
	for(int i=0;i<m;i++)g[i]=1LL*qpow(c,P-1-F(i))*A[i+len-1]%P;
	return g;
}

2.2 多项式多点求值

模板

多项式多点求值，即求多项式 (A(x)) 在点 (x_1,x_2,cdots,x_n) 上分别取到的值。

Sol 1

常用做法。

构造函数

[egin{aligned} P_0(x)&=prod_{i=1}^{lfloorfrac{n}{2} floor}(x-x_i)\ P_1(x)&=prod_{i=lfloorfrac{n}{2} floor+1}^{n}(x-x_i) end{aligned} ]

设 (A(x)=P_0(x)D(x)+R(x))，且 (deg R<deg P_0=lfloorfrac{n}{2} floor)。

那么对于 (forall xin {x_1,x_2,cdots,x_{lfloorfrac{n}{2} floor}})，都有 (A(x)=R(x))，于是我们就将一个 (deg =n) ，有 (n) 个点的问题，转化为一个 (deg <lfloorfrac{n}{2} floor) ，有 (lfloorfrac{n}{2} floor) 个点的问题。

另一半点值与上面同理。

因此分治 NTT 即可，注意计算 (P_0(x)) 和 (P_1(x)) 同样可以用一次分治 NTT 预处理。

设计算的复杂度为 (T(x))，则 (T(x)=2T(frac{x}{2})+O(nlog n))，此处 (O(nlog n)) 的部分是算 (D(x),R(x)) 的复杂度，容易发现预计算复杂度也是 (T(x))。

由主定理可得总复杂度为 (O(nlog^2 n))。

实际应用时可以通过用暴力秦九韶进行剪枝来优化常数。

Code

鸽了

Sol 2

转置做法。

先简单解释一下 转置原理 的核心思想：

对矩阵 (mathbf M) 和向量 (mathbf v)，为了快速计算 (mathbf {Mv})，我们可以先考察怎么计算 (mathbf M^mathsf Tmathbf v)，也就是矩阵的转置。设 (mathbf M) 可以分解为 (mathbf M=mathbf E_1 mathbf E_2cdots mathbf E_k)，那么 (mathbf M^mathsf T=mathbf E_1^mathsf T mathbf E_2^mathsf Tcdots mathbf E_k^mathsf T)。在这些初等矩阵中，它们的功能可以分为两类：

  1. (mathbf {Ev}) 的效果是让向量 (mathbf v) 的第 (i) 位乘上 (c)，那么其转置效果不变。
  2. (mathbf{Ev}) 的效果是让向量 (mathbf v) 的第 (i) 位乘上 (c) 然后加到第 (j) 位，那么它的转置的效果就是让向量的第 (j) 位乘上 (c) 然后加到第 (i) 位。

接下来我们考虑多点求值的过程，其本质是 Vander Monde 矩阵

[mathbf V(x_0,x_1,dots,x_{n-1})= egin{bmatrix} 1&x_0&x_0^2&cdots&x_0^{n-1}\ 1&x_1&x_1^2&cdots&x_1^{n-1}\ vdots&vdots&vdots&ddots&vdots\ 1&x_{n-1}&x_{n-1}^2&cdots&x_{n-1}^{n-1} end{bmatrix} ]

对应的线性变换 (mathbf{V}(x_0,x_1,dots,x_{n-1})mathbf v)，其中 (mathbf v) 是系数向量 (egin{bmatrix}v_0\v_1\vdots\v_{n-1}end{bmatrix})。

根据转置原理，我们考虑其转置 (mathbf{V}^mathsf T(x_0,x_1,dots,x_{n-1})mathbf v)：

[mathbf V^mathsf T(x_0,x_1,dots,x_{n-1})mathbf v= egin{bmatrix} 1&1&1&cdots&1\ x_0&x_1&x_2&cdots&x_{n-1}\ vdots&vdots&vdots&ddots&vdots\ x_0^{n-1}&x_1^{n-1}&x_2^{n-1}&cdots&x_{n-1}^{n-1} end{bmatrix}mathbf v ]

考虑这个转置所求的是什么。

第 (k) 项是

[sum_{i=0}^{n-1}x_i^{k}v_i=[x^k]sum_{i=0}^{n-1}v_i(x_ix)^k=[x^k]sum_{i=0}^{n-1}frac{v_i}{1-x_ix} ]

而为了求这个，我们可以这么做：

  1. 分治，维护左右两部分的 ((u_1,L)) 和 ((u_2,R))，也就是答案的分子和分母的部分，然后合并为 ((u_1R+u_2L,LR=P))。
  2. 答案就是 (frac{u}{P}=uP^{-1})，这里 (P) 指的是分母，即 (prod_i(1-x_ix))。

我们只要算出其转置，就可以得到新的多点求值做法。在此之前，我们还要考虑一下多项式乘法 (mathbf{MUL}(A)mathbf v) 的转置 (mathbf {MUL}(A)^mathsf Tmathbf v)。

对多项式 (A(x)=sum_{i}a_ix^i)，在多项式乘法中会把每个 (v_j) 乘上 (a_i) 然后贡献给 (i+j)，因此根据转置原理，转置的多项式乘法就是把每个 (v_{i+j}) 乘上 (a_i) 然后贡献给 (i)。可以看到，这就是一个标准的减法卷积。此外，如果原来的变换没有溢出部分，那么转置后的溢出部分我们也要扔掉。

于是，我们就可以得到新的多点求值做法：

  1. 整体分治（其实就是线段树的 build），算出每个线段树节点对应的区间里 ((1-x_ix)) 的乘积。
  2. 对要求的 (m-1) 次多项式，我们对它计算 (mathbf{MUL}(P^{-1}mod x^m)^mathsf T) 并保留前 (n) 位。
  3. 从线段树自顶向下递归，令下传的两个向量分别为 (mathbf l=mathbf {MUL}(R)^mathsf Tmathbf v) 和 (mathbf r=mathbf{MUL}(L)^mathsf Tmathbf v)。
  4. 最后得到的叶节点的向量长度均为 (1)，对应于该处的点值。

新做法不需要多项式取模，而且常数也有显著提升。

Code

鸽了

2.3 多项式快速插值

模板

多项式快速插值，即给定 (n) 个点 ((x_i,y_i))，你需要求出一个多项式 (f(x))，使得 (deg f<n) 且 (forall i,f(x_i)=y_i)。

首先根据拉格朗日插值公式可得

[egin{aligned} f(x)&=sum_{i=1}^{n}y_iprod_{i eq j}frac{x-x_j}{x_i-x_j}\ &=sum_{i=1}^{n}frac{y_i}{prod_{i eq j}(x_i-x_j)}prod_{i eq j}(x-x_j) end{aligned} ]

这时如果你直接模拟那么复杂度是 (O(n^2)) 的，我们考虑如何优化。

先考虑系数部分的

[prod_{i eq j}(x_i-x_j) ]

不难发现如果设

[P(x)=prod_{i}(x-x_i) ]

那么

[prod_{i eq j}(x_i-x_j)=lim_{x o x_i}frac{P(x)}{x-x_i}=P'(x_i) ]

（最后一步是导数的定义）

那么使用多点求值就可以做到 (O(nlog^2n))。

下设 (frac{y_i}{P'(x_i)}=v_i)。

考虑和多点求值类似的做法，我们还是构造函数

[egin{aligned} P_0(x)&=prod_{i=1}^{lfloorfrac{n}{2} floor}(x-x_i)\ P_1(x)&=prod_{i=lfloorfrac{n}{2} floor+1}^{n}(x-x_i) end{aligned} ]

设

[egin{aligned} f_0(x)&=sum_{i=1}^{lfloorfrac{n}{2} floor}v_iprod_{j eq i,jle lfloorfrac{n}{2} floor}(x-x_j)\ f_1(x)&=sum_{i=lfloorfrac{n}{2} floor+1}^{n}v_iprod_{j eq i,j>lfloorfrac{n}{2} floor}(x-x_j) end{aligned} ]

那么容易发现

[f(x)=f_0(x)P_1(x)+f_1(x)P_0(x) ]

分治 NTT 即可。

设这部分复杂度为 (T(x))，则 (T(x)=2T(frac{x}{2})+O(nlog n))，此处 (O(nlog n)) 的部分是计算 (f(x)) 的复杂度。由于 (P(x)) 在多点求值时已经算过，所以不需再算。

由主定理可得总复杂度为 (O(nlog^2 n))。

Code

鸽了

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

给定普通多项式

[F(x)=sum_{i=0}^{n-1}a_ix^i ]

求下降幂多项式

[G(x)=sum_{i=0}^{n-1}b_ix^underline i ]

使得 (F(x)=G(x))。

首先有

[x^k=sum_{i=0}^{k}egin{Bmatrix}k\iend{Bmatrix}x^{underline i} ]

所以

[egin{aligned} F(x)&=sum_{k=0}^{n-1}a_kx^k\ &=sum_{k=0}^{n-1}sum_{i=0}^{k}a_iegin{Bmatrix}k\iend{Bmatrix}x^{underline i}\ &=sum_{i=0}^{n-1}(sum_{k=i}^{n-1}a_iegin{Bmatrix}k\iend{Bmatrix})x^{underline i} end{aligned} ]

所以

[egin{aligned} b_k&=sum_{i=k}^{n-1}a_iegin{Bmatrix}i\kend{Bmatrix}\ &=sum_{i=0}^{n-1}a_iegin{Bmatrix}i\kend{Bmatrix}\ &=sum_{i=0}^{n-1}a_isum_{t=0}^{k}frac{t^i(-1)^{k-t}}{t!(k-t)!}\ &=sum_{t=0}^{k}frac{sum_{i=0}^{n-1}a_it^i}{t!}frac{(-1)^{k-t}}{(k-t)!}\ &=sum_{t=0}^{k}frac{F(t)}{t!}frac{(-1)^{k-t}}{(k-t)!} end{aligned} ]

多点求值预处理 (F(t)) ，然后卷积即可。

复杂度 (O(nlog ^2n))。

Code

鸽了

2.5 下降幂多项式乘法

给定 (n) 次下降幂多项式 (A(x)) 和 (m) 次下降幂多项式 (B(x))，求一个 (n+m) 次的下降幂多项式 (F(x))，使 (F(x)=A(x)B(x))。

对于下降幂多项式 (F(x))，考虑它的点值的 EGF

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

当 (F(x)=x^underline c) 时

[egin{aligned} F^#&=sum_{i=0}^{infty}frac{i^underline c}{i!}x^i\ &=sum_{i=0}^{infty}frac{x^i}{(i-c)!}\ &=x^csum_{i=0}^{infty}frac{x^i}{i!}\ &=e^x imes x^c end{aligned} ]

设

[F(x)=sum_{i=0}^{infty}a_ix^underline i ]

则

[egin{aligned} F^#(x)&=sum_{i=0}^{infty}a_ix^ie^x\ &=G(x)e^x end{aligned} ]

其中

[G(x)=sum_{i=0}^{infty}a_ix^i ]

也就是说，(F^#) 就是把 (F) 当成普通多项式，乘上 (e^x) 的结果。

同理可得其逆运算就是 (e^{-x})。

点值 EGF 点乘即可，(e^x) 和 (e^{-x}) 可以手算。

复杂度 (O(nlog n))。

Code 
void FDT(vec&A,int len,int tp){
	init(len<<1);
	vec ee(lmt);
	if(A.size()<lmt)A.resize(lmt);
	if(tp==-1)for(int i=0;i<lmt;i++)A[i]=1LL*A[i]*invfac[i]%P;
	for(int i=0;i<len;i++){
		if(tp==-1&&i&1)ee[i]=P-invfac[i];
		else ee[i]=invfac[i];
	}
	for(int i=len;i<lmt;i++)ee[i]=A[i]=0;
	NTT(A,lmt,1);NTT(ee,lmt,1);
	for(int i=0;i<lmt;i++)A[i]=1LL*A[i]*ee[i]%P;
	NTT(A,lmt,-1);
	if(tp==1)for(int i=0;i<lmt;i++)A[i]=1LL*A[i]*fac[i]%P;
	for(int i=0;i<lmt;i++)ee[i]=0;
}
vec mulDown(vec f,vec g,int len){
	FDT(f,len,1);FDT(g,len,1);
	for(int i=0;i<len;i++)f[i]=1LL*f[i]*g[i]%P;
	FDT(f,len,-1);
	return f;
}

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

给定下降幂多项式

[F(x)=sum_{i=0}^{n-1}a_ix^underline i ]

求普通多项式

[G(x)=sum_{i=0}^{n-1}b_ix^i ]

使得 (F(x)=G(x))。

根据上题结论，下降幂多项式的点值是与 (e^x) 的卷积。

那我们只要求出 (F(x)) 在 (0,1,dots,n-1) 的点值，然后用多点求值就可以得到原多项式。

复杂度 (O(nlog^2 n))。

2.7 多项式复合

2.8 多项式复合逆

2.9 快速沃尔什变换

给定序列 (A) 和 (B)，求

[C_i=sum_{joplus k=i}A_j imes B_k ]

其中 (oplus) 是位运算

记对 (A) 进行沃尔什变换后的序列为 (operatorname{FWT}(A))，那么有

[operatorname{FWT}(C)=operatorname{FWT}(A)cdot operatorname{FWT}(B) ]

其中 (cdot) 表示点乘。

下面分与、或、异或三种进行讨论。

2.9.1 或

[C_i=sum_{j| k=i}A_j imes B_k ]

显然可得

[j|i=i,k|i=iiff (j|k)|i=i ]

构造

[operatorname{FWT}(A)_i=sum_{j|i=i}A_j ]

所以

[egin{aligned} operatorname{FWT}(A)_ioperatorname{FWT}(B)_i&=sum_{k|i=i}a_j imes sum_{j|i=i}b_k\ &=sum_{j|i=i}sum_{k|i=i}a_jb_k\ &=sum_{(j|k)|i=i}a_jb_k\ &=sum_{t|i=i}sum_{j|k=t}a_jb_k\ &=sum_{t|i=i}c_t\ &=operatorname{FWT}(C)_i end{aligned} ]

2.10 常系数齐次线性递推

模板

常系数齐次线性递推，是指给定 (f[1,2,dots,k]) 和 (a[0,1,dots,k-1])，且对 (forall mge k)，都有

[a_m=sum_{i=1}^{k}f_ia_{m-i} ]

求 (a_n) 的值。

先考虑一般是如何处理这个问题的。

考虑矩阵

[A= egin{bmatrix} f_1 & f_2 & f_3 & cdots & f_{k-1} & f_k\ 1 & 0 & 0 & cdots & 0 & 0\ 0 & 1 & 0 & cdots & 0 & 0\ vdots & vdots & vdots & ddots & vdots & vdots\ 0 & 0 & 0 & cdots & 1 & 0 end{bmatrix} ]

那么

[egin{bmatrix} a_n\ a_{n-1}\ vdots\ a_{n-k+1} end{bmatrix} =egin{bmatrix} a_{n-1}\ a_{n-2}\ cdots\ a_{n-k} end{bmatrix} imes A ]

所以

[egin{bmatrix} a_{n}\ a_{n-1}\ vdots\ a_{n-k+1} end{bmatrix} =egin{bmatrix} a_{k-1}\ a_{k-2}\ cdots\ a_{0} end{bmatrix} imes A^{n-k+1} ]

使用矩阵快速幂就可以做到 (O(k^3log n)) 的复杂度。

考虑如何优化这个过程，由于我们只要求 (a_n)，所以我们只关心右式的第一项即可。

下记 (m=n-k+1)，且

[S=egin{bmatrix} a_{k-1}\ a_{k-2}\ cdots\ a_{0} end{bmatrix} ]

现在假设我们不知道从哪找来一个数组 (c)，使得

[A^m=sum_{i=0}^{k-1}c_iA^i ]

则

[egin{aligned} a_n&=(S imes A^m)_0\ &=(S imes sum_{i=0}^{k-1}c_iA^i)_0\ &=(sum_{i=0}^{k-1}c_iS imes A^i)_0\ &=sum_{i=0}^{k-1}c_i(S imes A^i)_0\ &=sum_{i=0}^{k-1}c_ia_{i+k-1} end{aligned} ]

2.11 常系数非齐次线性递推

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/happydef/p/poly2.html