隐藏
多项式运算学习笔记 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

多项式运算学习笔记

发表于 更新于 分类于 Valine：

多项式

有关多项式的知识在FFT处有详细的讲解。

下文的$A(x),B(x),F(x)$均为多项式，简记为$A,B,F$。
其系数表示为$(a_i),(b_i),(f_i)$，点值表示为$(x,A(x)),(x,B(x)),(x,F(x))$。
本文中若无特殊说明，多项式均为$n$项。
使用$deg_A$表示多项式$A$的次数，本文中若无特殊说明，$deg_A=n-1$。

多项式的运算

多项式加法

故$A+B$的系数表示为$(a_i+b_i)$。
可以在$O(n)$的时间内完成运算。

多项式乘法

利用上式的系数表示可以在$O(n^2)$的时间内完成运算。

使用上式的系数表示可以在$O(n)$的时间内完成运算。

使用FFT可以在$O(n\log n)$的时间内将系数表示与点值表示进行转换。

多项式取模

多项式只能模一个多项式，模一个数无意义。
多项式模多项式还是一个多项式。
通常，使用多项式模$x^n$表示取该多项式的前$n$位（$[0,n-1]$）。

多项式求逆

若存在$B(x)$（不一定为$n$项），满足$deg_B\le deg_A$，使得：

则称$B(x)$为$A(x)$在$\bmod {x^n}$意义下的逆元，记作$A^{-1}(x)$。

在求逆过程中，假设$n$为$2$的整数幂次，若不满足可将多项式高位补$0$达到$n$项。

当$n=1$时，$A(x)\equiv c\pmod x$，$c$是一个常数，故$A^{-1}(x)=c^{-1}$。
当$n\gt1$时，有：

假设在$\bmod x^{\frac n2}$意义下$A^{-1}(x)=B’(x)$已求出，则：

将$(1)$放到$\bmod x^{\frac n2}$的意义下，仍然有：

用$(2)-(3)$可得：

两边同时平方得：

解释一下为什么平方后模的$x^\frac n2$也会平方。
因为$B(x)-B’(x)$在模意义下为$0$，说明其$[0,\frac n2-1]$项系数均为$0$，平方后，系数为$a_i=\sum_{j=0}^ia_ja_{i-j}$，显然$j,i-j$间有一个$\lt\frac n2$，因此$a_i$也为$0$，故在$\bmod x^{n}$意义下仍为$0$。
同时乘上$A(x)$，可以得到：

这样就可以得到$\bmod x^n$意义下的逆元了，使用FFT加速多项式乘法可以在$O(n\log n)$的时间内完成当前层递归。
故总时间复杂度为：

使用主定理可知：

可看出，多项式是否存在逆元取决于其常数项是否存在逆元。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void polynomial_inverse(const LL* a,const int n,LL* b) { //保证n是2的整数幂
	if(n==1) {
		b[0]=inv(a[0]);
		return;
	}
	polynomial_inverse(a,n>>1,b);
	int p=n<<1;
	static LL x[maxn];
	copy(a,a+n,x),fill(x+n,x+p,0);
	ntt.init(p),ntt.dft(x),ntt.dft(b);
	for(int i=0; i<p; i++)b[i]=b[i]*((2-x[i]*b[i]%mod+mod)%mod)%mod;
	ntt.idft(b),fill(b+n,b+p,0);
}

void solve(const LL* a,const int n,const LL* b) { //n是多项式项数
	int p=1;
	while(p<n)p<<=1;
	polynomial_inverse(a,p,b);
	fill(b+n,b+p,0);
}

多项式开根

若存在多项式$B(x)$，使得：

则称$B(x)$是$A(x)$的根。

在求多项式根的一组合法解时，假设$n$为$2$的整数幂次，若不满足可将多项式高位补$0$达到$n$项。

当$n=1$时，若$A(0)$是个变量，可能需要用到二次剩余。
当$n\gt1$时，有：

假设在$\bmod x^{\frac n2}$意义下$\sqrt{A(x)}=B’(x)$已求出，则：

将$(4)$放到$\bmod x^{\frac n2}$的意义下，仍然有：

用$(5)-(6)$可得：

两边同时平方得：

提出完全平方项得：

同时开方可以得到一组合法解：

使用$(4)$代换可得：

这样就可以得到$\bmod x^n$意义下的多项式根了，使用FFT加速多项式乘法与多项式求逆可以在$O(n\log n)$的时间内完成当前层递归。
故总时间复杂度为：

使用主定理可知：

可看出，多项式的根是否存在取决于其常数项是否存在二次剩余。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void polynomial_sqrt(const LL* a,const int n,LL* b) { //保证n是2的整数幂
	if(n==1) {
		b[0]=cal(a[0]);
		return;
	}
	polynomial_sqrt(a,n>>1,b);
	int p=n<<1;
	static LL inv_b[maxn],x[maxn];
	fill(inv_b,inv_b+p,0);
	polynomial_inverse(b,n,inv_b);
	copy(a,a+n,x),fill(x+n,x+p,0);
	ntt.init(p),ntt.dft(x),ntt.dft(b),ntt.dft(inv_b);
	for(int i=0; i<p; i++)b[i]=(x[i]*inv_b[i]%mod+b[i])%mod*inv2%mod;
	ntt.idft(b),fill(b+n,b+p,0);
}

void solve(const LL* a,const int n,const LL* b) { //n是多项式项数
	int p=1;
	while(p<n)p<<=1;
	polynomial_sqrt(a,p,b);
	fill(b+n,b+p,0);
}

多项式求导

根据一元函数$f(x)=ax^2+bx+c$的求导规则$f’(x)=2ax+b$可知：
多项式求导即将幂系数放下来并左移一位，举个栗子：

时间复杂度$O(n)$，代码中的$n$是项数。 

1
2
for(int i=0; i<n-1; i++)b[i]=1ll*a[i+1]*(i+1)%mod;
b[n-1]=0;

多项式积分

多项式积分就是求导的逆运算，将系数重新放回上标，并右移一位，举个栗子：

时间复杂度$O(n)$，代码中的$n$是项数。 

1
2
for(int i=n-1; i>=1; i--)b[i]=1ll*b[i-1]*inv[i]%mod;
b[0]=0;

牛顿迭代法

已知函数$G(x)$，要求一个多项式$F(x)\bmod x^n$，满足：

在求牛顿迭代法的一组合法解时，假设$n$为$2$的整数幂次，若不满足可将多项式高位补$0$达到$n$项。

当$n=1$时，$G(F(x))\equiv\pmod x$，需要单独计算。
当$n\gt1$时，有：

假设在$\bmod x^{\frac n2}$意义下的解$F_0(x)$已求出，则：

将$G(F(x))$在$F_0(x)$处进行泰勒展开，得到：

根据$(8)$可知，$(F(x)-F_0(x))^2$的最低非$0$项次数大于$2\frac n2$，所以有：

根据$(7)$可知：

若计算多项式嵌套的时间复杂度为$O(C(n))$，根据主定理可知总复杂度仍然为$O(C(n))$。
然而计算多项式嵌套的最优时间复杂度为$O((n\log n)^{1.5})$，因此用它直接解题是无卵用的，不妨考虑构造$G(x),F(x)$去解决一些特殊的问题。

使用牛顿迭代法计算多项式开根

多项式开根可以使用牛顿迭代法计算。

不妨构造$F^2(x)-A(x)=0$，目的要求解$F(x)\pmod {x^n}$。
此时$G(F(x))=F^2(x)-A(x),G’(F(x))=2F(x)$，代入上述方程可得：

与上面推的式子结果相同。

多项式lnp与exp

多项式的对数有什么意义？可以理解为多项式与麦克劳林级数的复合。

根据麦克劳林级数有：

因此对于多项式$F(x)$有：

多项式lnp

对于多项式$A(x)$，现在我们要计算其对数$\ln A(x)$。
我们可以对其求导再积分：

根据链式法则可知：

那么这里需要用到多项式求逆与多项式求导。

这里需要用到多项式积分。

不难得到，多项式lnp的时间复杂度为$O(n\log n)$。

多项式exp

对于多项式$A(x)$，现在我们要计算其对数$e^{A(x)}$。
其中$A(0)=0$。
现在不能再用上面求导再积分的方法了，因为指数函数求导得到本身。
这时就需要利用牛顿迭代法。
构造$F(x)=e^{A(x)}$。
变形得到：

故构造$G(F(x))=\ln F(x)-A(x)$，此时$G’(F(x))=\frac1{F(x)}$，因此：

当$n=1$的时候，$F(x)$的常数项为$e^0=1$。

时间复杂度为： 

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
35
36
37
void Multiply(const int* a1,const int n1,const int* a2,const int n2,int* ans) {
	int n=1;
	while(n<n1+n2)n<<=1;
	static int c1[maxn],c2[maxn];
	copy(a1,a1+n1,c1),fill(c1+n1,c1+n,0);
	copy(a2,a2+n2,c2),fill(c2+n2,c2+n,0);
	ntt.dft(c1);
	ntt.dft(c2);
	for(int i=0; i<n; i++)c1[i]=1ll*c1[i]*c2[i]%mod;
	ntt.idft(c1);
	for(int i=0; i<n1+n2-1; i++)ans[i]=c1[i];
}

void polynomial_lnp(const int* a,int n,int* b) {
	static int tmp[maxn];
	polynomial_inverse(a,n,tmp);
	for(int i=0; i<n-1; i++)b[i]=1ll*a[i+1]*(i+1)%mod;
	b[n-1]=0;
	Multiply(b,n,tmp,n,b);
	fill(b+n,b+(n<<1),0),fill(tmp,tmp+n,0);
	for(int i=n-1; i>=1; i--)b[i]=1ll*b[i-1]*inv[i]%mod;
	b[0]=0;
}

void polynomial_exp(const int *a,int n,int* b) {
	if(n==1) {
		b[0]=1;
		return;
	}
	polynomial_exp(a,n>>1,b);
	int p=n<<1;
	static int x[maxn];
	polynomial_lnp(b,n,x);
	for(int i=0; i<n; i++)x[i]=-x[i]+a[i],check(x[i]);
	add(x[0],1);
	Multiply(b,n,x,n,b),fill(b+n,b+p,0);
}

多项式$k$次幂

给出一个多项式$A(x)$，要求计算$A^k(x),k\in\mathbb Q$。
若$k\in\mathbb N$，可以使用快速幂计算，时间复杂度为$O(n\log n\log k)$，注意不要每次乘法的时候都执行$idft$，否则常数巨大。

利用对数可以将指数部分提作系数的性质，可知：

需要用到多项式exp与多项式lnp，时间复杂度仍为$O(n\log n)$。
多项式开根也可以这么计算。

参考资料

相关文章
姥爷们赏瓶冰阔落吧~