多项式基础操作学习笔记

发表于

“做多项式题就像嗑药，出多项式题就像贩毒。” —— 某福建知名OI选手

前置知识与约定

  • 多项式乘法,我们可以用FFT/NTT解决.
  • 简单求导/微积分(简单的意思是如果这都不会就不要说自己学过了)
  • $[P]$表示艾弗森括号,当$P$为真时表达式的值为$1$，$P$为假时表达式的值为$0$
  • $\Gamma$表示阶乘函数, $e$表示自然底数
  • $f^{(n)}$表示函数$f(x)$的$n$阶导函数

多项式乘法

我们可以用FFT/NTT在$\mathcal O(n \log n)$的时间内解决, 但两者优劣势不尽相同.

FFT的缺点在于使用复数,精度差,使用单位根,常数大等.

而NTT的缺点在于必须在模数的原根较特殊的情况下才能使用(如$998244353$等).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void NTT(int *f, int type) {
	for(int i = 0; i < n; ++i) if(i < rev[i]) std::swap(f[i], f[rev[i]]);
	for(int i = 1; i < n; i <<= 1) {
		int tk = quick_power(3, (mod - 1) / (i << 1));
		for(int j = 0; j < n; j += (i << 1)) {
			int t = 1, x, y;
			for(int k = 0; k < i; ++k, t = 1ll * t * tk % mod) {
				x = f[j + k], y = 1ll * t * f[j + k + i] % mod;
				f[j + k] = (x + y) % mod; f[j + k + i] = (x - y + mod) % mod;
			}
		}
	}
	if(type == 1) return ;
	int inv = quick_power(n, mod - 2);
	std::reverse(f + 1, f + n);
	for(int i = 0; i < n; ++i) f[i] = 1ll * f[i] * inv % mod;
}

多项式泰勒展开

如果函数$f(x)$在$x_0$处存在$n$阶导数,那么定义$f(x)$在$x = x_0$处的$\rm Taylor$展开式为:

$$f(x) = \sum_{i=0}^n \frac {f^{(n)}(x_0)}{\Gamma(i)} (x - x_0)^i + R_n(x)$$

其中$R_n(x)$表示拉格朗日余项,即$(x - x_0)^n$的高阶无穷小.

一个例子:$e^x = 1 + \frac {x}{\Gamma(1)} + \frac {x^2}{\Gamma(2)} + \cdots$

多项式牛顿迭代

牛顿迭代可以用来求函数的零点,而多项式牛顿迭代可以求多项式函数的零点.

即对于一个多项式$F(x)$, 求一个多项式$G_k(x)$满足$F(G_k(x)) \equiv 0 \pmod{2^k}$

假设我们已经求出了$G_{k-1}(x)$,考虑如何推得$G_k(x)$

我们把$F(G_k(x))$在$x = G_{k-1}(x)$处进行$\rm Taylor$展开,可以得到:

$$F(G_k(x)) = F(G_{k-1}(x)) + \frac {F’(G_{k-1}(x))}{\Gamma(1)} (G_k(x) - G_{k-1}(x))$$

化简,移项得:

$$G_k(x) = G_{k-1}(x) - \frac {F(G_{k-1}(x))}{F’(G_{k-1}(x))}$$

多项式求逆

已知$F(x)$,求$G(x)$满足$F(x)G(x) \equiv 1 \pmod{x^n}$

和推牛顿迭代的式子一样,我们假设已经求出了$G_0(x)$满足:

$$F(x)G_0(x) \equiv 1 \pmod{x^{\lfloor \frac {2}{n}\rfloor}}$$

由题目条件可得:

$$F(x)G(x) \equiv 1 \pmod{x^{\lfloor \frac {2}{n}\rfloor}}$$

上下两式相减可得:

$$F(x)G_0(x) - F(x)G(x) \equiv 0 \pmod{x^{\lfloor \frac {2}{n}\rfloor}}$$

同余式两边同时除以$F(x)$可得:

$$G_0(x) - G(x) \equiv 0 \pmod{x^{\lfloor \frac {2}{n}\rfloor}}$$

同余式两遍平方可得:

$$G_0(x)^2 - 2G(x)G_0(x) + G(x)^2 \equiv 0 \pmod{x^n}$$

由题目条件,同余时两边同时乘$F(x)$得:

$$F(x)G_0(x)^2 - 2G_0(x) + G(x) \equiv 0 \pmod{x^n}$$

把式子移项,可得:

$$G(x) = 2G_0(x) - F(x)G_0(x)^2 \equiv 0 \pmod{x^n}$$

递归求解即可.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void PolyInv(int *f, int *g, int len) {
	if(len == 1) {g[0] = quick_power(f[0], mod - 2); return ;}
	PolyInv(f, g, (len + 1) >> 1);
	n = 1, m = 0;
	while(n < (len << 1)) {n <<= 1; ++m;}
	for(int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (m - 1));
	for(int i = 0; i < len; ++i) c[i] = f[i];
	for(int i = len; i < n; ++i) c[i] = 0;
	NTT(c, 1); NTT(g, 1);
	for(int i = 0; i < n; ++i) g[i] = 1ll * (2 - 1ll * c[i] * g[i] % mod + mod) % mod * g[i] % mod;
	NTT(g, -1);
	for(int i = len; i < n; ++i) g[i] = 0;
}

多项式求导

没啥好说的吧, 给出公式:

$$x^{a^{\prime}} = ax^{a-1}$$

Code

1
2
3
4
inline void PolyDer(int *f, int *g, int len) {
	for(int i = 1; i < len; ++i) g[i - 1] = 1ll * i * f[i] % mod;
	g[len - 1] = 0;
}

多项式积分

根据牛顿-莱布尼兹公式:

$$\int x^a {\rm d}x = \frac {1}{a+1} x^{a+1}$$

Code

1
2
3
4
inline void PolyInt(int *f, int *g, int len) {
	for(int i = 1; i < len; ++i) g[i] = 1ll * f[i - 1] * quick_power(i, mod - 2) % mod;
	g[0] = 0;
}

多项式对数函数

即多项式求$\ln$

已知$F(x)$,求$G(x)$满足$G(x) \equiv \ln F(x) \pmod{x^n}$

设函数$H(x) = \ln x$,那么同余式右边即为$H(F(x))$.

考虑将同余式两边求导,可得:

$$G’(x) \equiv H’(x) \pmod{x^n}$$

即:

$$G’(x) \equiv \frac{F’(x)}{F(x)} \pmod{x^n}$$

那么我们把$F(x)$求个导,再求个逆,然后把得到的两个多项式求一下卷积.

这样我们得到的是$G’(x)$,然后再把他积回去即可.

Code

1
2
3
4
5
6
7
8
9
inline void PolyLn(int *f, int *g, int len) {
	PolyDer(f, a, len); PolyInv(f, b, len);
	n = 1; m = 0;
	while(n < (len << 1)) {n <<= 1; ++m;}
	for(int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (m - 1));
	NTT(a, 1); NTT(b, 1);
	for(int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % mod;
	NTT(a, -1); PolyInt(a, g, len);
}

多项式指数函数

即多项式求$\rm exp$

已知$F(x)$,求$G(x)$满足$G(x) \equiv \exp (F(x)) \pmod{x^n}$.

考虑同余式两边同时取自然对数:

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

移项,可得:

$$\ln G(x) - F(x) \equiv 0 \pmod{x^n}$$

将这个式子套进 多项式牛顿迭代 可得:

$$G(x) \equiv G_0(x) - \frac {\ln G_0(x) - F(x)}{\frac {1}{G_0(x)}}$$

化简可得:

$$G(x) \equiv G_0(x) - (\ln G_0(x) - F(x)) \times G_0(x) \pmod {x^n}$$

$$G(x) \equiv G_0(x) \times (1 - \ln G_0(x) + F(x)) \pmod {x^n}$$

递归+多项式Ln计算即可.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void PolyExp(int *f, int *g, int len) {
	if(len == 1) {g[0] = 1; return ;}
	PolyExp(f, g, (len + 1) >> 1);
	n = 1; m = 0;
	while(n < (len << 1)) {n <<= 1; ++m;}
	for(int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (m - 1));
	for(int i = 0; i < (len << 1); ++i) d[i] = e[i] = 0;
	PolyLn(g, d, len); 
	for(int i = 0; i < len; ++i) e[i] = f[i];
	NTT(g, 1); NTT(d, 1); NTT(e, 1);
	for(int i = 0; i < n; ++i) g[i] = (1ll - d[i] + e[i] + mod) * g[i] % mod;
	NTT(g, -1); 
	for(int i = len; i < n; ++i) g[i] = 0;
}

多项式快速幂

已知$F(x)$,求$G(x)$满足$G(x) \equiv F(x)^k \pmod{x^n}$

首先我们在初中阶段就应该学过这样一个式子:

$$\log_a b^k = k \log_a b$$

这个式子对多项式也成立,

那么我们只需要把$F(x)$求一个$\ln$,然后把它乘上$k$,最后再$\exp$回去即可.

Code

1
2
3
4
5
6
inline void PolyPow(int *f, int *g, int k, int len){
	PolyLn(f, h, len);
	for(int i = 0; i < len; ++i) h[i] = 1ll * h[i] * k % mod;
	PolyExp(h, g, len);
	for(int i = 0; i < len; ++i) h[i] = 0;
}

多项式开根

已知$F(x)$,求$G(x)$满足$G(x)^2 \equiv F(x) \pmod{x^n}$

和多项式求逆类似,利用那个结论,得到:

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

那么我们先把$F(x)$求个$\ln$,然后把它的系数乘以$2$的逆元,最后再$\exp$回去即可.

Code

1
2
3
4
5
6
7
inline void PolySqr(int *f, int *g, int len) {
	PolyLn(f, l, len);
	int invt = quick_power(2, (mod - 2));
	for(int i = 0; i < len; ++i) l[i] = 1ll * l[i] * invt % mod;
	PolyExp(l, g, len);
	for(int i = 0; i < len; ++i) l[i] = 0;
}

更新日志&引用

  • 2019/9/27, 更新至多项式求逆
  • 2019/9/28, 更新至多项式开根
  • 2019/9/28, To do 多项式除法&取模

作者是完完全全跟着Venus和M-sea大爷学的多项式,所以本篇文章有很多引用来自她们的博客.

再次感谢这两篇博客给予本菜鸡在多项式学习方面的帮助!

摘要来自NaCly_Fish的Luogu个人空间.

To be continue