浅谈多项式
CYJian
2019-01-24 19:38:51
# 浅谈多项式
大概涉及一些多项式的运算，算是多项式里面比较基础的内容吧。
## 前置知识
1. FFT
2. NTT
3. 多项式求导
4. 简单的积分
~~如果会，可以直接跳过。。~~
如果还不会NTT，推荐学习[这一篇博客](https://oi.men.ci/fft-to-ntt/)，如果连FFT都不会，请先学会FFT，推荐食用[这篇博客](https://www.luogu.org/blog/command-block/fft-xue-xi-bi-ji)或者[这篇博客](https://oi.men.ci/fft-notes/)
### 多项式求导
不严谨的说，一个函数在一个位置的导数就是这个位置上切线的斜率。。
这里需要的多项式求导的知识非常简单，好像只要知道下面五个式子就够了。。(注:这里的$'$表示求导的意思)
$$f(x)=e^x \qquad f'(x)=e^x$$
$$f(x)=ln\ x \qquad f'(x)=\frac{1}{x}$$
$$f(x)=ax^t \qquad f'(x)=atx^{t-1}$$
$$(f(x) \pm g(x))'=f'(x) \pm g'(x)$$
$$(f(g(x)))'=f'(g(x)) \ast g'(x)$$
所以我们可以推出多项式求导的公式：
$$f(x)=\sum_{i=0}^{n}a_ix^i \qquad f'(x)=\sum_{i=0}^{n-1}(i+1)a_{i+1}x^i$$
### 多项式积分
这里不说多难，也不求非常严谨，能做出题就行。
对于这样一个导数：
$$f'(x)=\sum_{i=0}^{n}a_ix^i$$
我们想要知道它原来的函数怎么办？？
积分啊。。
这里也只给公式，不深入探究(毕竟这里不是重点，待会只用结论就好)
(其实也就是求导的逆过程)
$$f(x)=\sum_{i=1}^{n+1}\frac{a_{i-1}x^i}{i}$$
(当然，上面的多项式是满足求导的结果是这个导数的一个最为简单的多项式。)
------
## 进入正题
好的，这里大概会讲如下的多项式有关的知识点：
1. 多项式求逆
2. 多项式求$ln$
3. 多项式复合
4. 多项式求$exp$
5. 多项式快速幂
6. 多项式除法
> Tips：这里的知识一环套一环，如果不会前面的后面的基本上得凉凉。。(除非你是天才)
~~有点小多啊。。~~
不啰嗦了直接开始吧。
### 多项式求逆
#### 问题$1$描述
给出多项式$A(x)$，求一个多项式$B(x)$使得$A(x) \ast B(x) \equiv 1\ (mod\ x^n)$
#### 问题$1$分析
假设我们现在已经有了一个多项式$C(x)$，满足
$$A(x) \ast C(x) \equiv 1 \ (mod\ x^{\lceil \frac{n}{2} \rceil})$$
然后我们要求的$B(x)$也满足：
$$A(x) \ast B(x) \equiv 1\ (mod\ x^n)$$
变形一下也可以得到:
$$A(x) \ast B(x) \equiv 1 (mod\ x^{\lceil \frac{n}{2} \rceil})$$
至于为什么可以这么做，稍加思考一下也可以想出来吧。。
因为如果在模$x^n$的意义下$A(x) \ast B(x)$的结果是1的话，说明了$x$的$1$次幂一直到$n-1$次幂的系数都是$0$。这样一来这么转化也是可以的。
那么我们就可以继续操作了。
$$A(x) \ast (B(x) - C(x)) \equiv 0\ (mod\ x^{\lceil \frac{n}{2} \rceil})$$
因为$A(x)$一定不会为$0$(不然不可能求出逆啊。。)，那么我们就可以得知：
$$B(x) - C(x) \equiv 0 \ (mod\ x^{\lceil \frac{n}{2} \rceil})$$
平方一下：
$$B^2(x) \equiv 2B(x) \ast C(x) - C^2(x)\ (mod\ x^n)$$
然后两边再乘上一个$A(x)$：
$$A(x) \ast B^2(x) \equiv 2A(x) \ast B(x) \ast C(x) - A(x) \ast C^2(x)\ (mod\ x^n)$$
然后由$A(x) \ast B(x) \equiv 1\ (mod\ x^n)$得知：
$$B(x) \equiv 2C(x) - A(x) \ast C^2(x)\ (mod\ x^n)$$
这样一来，$A(x)$和$C(x)$我们都知道，那么$B(x)$也可以知道了。
然后算法也非常明显了：倍增。
特别的，当$C(x)$仅有一项(常数项)的时候，这个值就是$A(x)$的常数项的逆元。(和之前的东西也不相悖)
那么我们就有一个$O(nlogn)$的求多项式的逆的算法了。
这里给出求逆的代码。。
```
inline void init(reg int n) {
N = 1; while(N <= (n << 1)) N <<= 1;
for(reg int i = 0; i < N; i++)
pos[i] = (pos[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
} // 预处理出NTT的多项式长度和NTT交换的位置
inline int quick_pow(reg int a, reg int k) {
reg int s = 1;
while(k) {
if(k & 1) s = (1LL * s * a) % mod;
a = (1LL * a * a) % mod;
k >>= 1;
}
return s;
}
inline void NTT(reg int a[], reg int k) {
for(reg int i = 0; i < N; i++)
if(i < pos[i]) swap(a[i], a[pos[i]]);
for(reg int l = 2; l <= N; l <<= 1) {
reg int len = l >> 1;
reg int delta = quick_pow(G, (mod - 1) / l);
for(reg int i = 0; i < N; i += l) {
reg int g = 1;
for(reg int j = i; j < i + len; j++) {
reg int tmp = 1LL * g * a[j + len] % mod;
a[j + len] = (a[j] - tmp + mod) % mod;
a[j] = (a[j] + tmp) % mod;
g = 1LL * g * delta % mod;
}
}
}
if(k) return ;
reg int prd = quick_pow(N, mod - 2); reverse(a + 1, a + N);
for(reg int i = 0; i < N; i++) a[i] = 1LL * a[i] * prd % mod;
} // 对N进行NTT。。
inline void GetNi(reg int A[], reg int B[], reg int n) {
if(n == 1) { B[0] = quick_pow(A[0], mod - 2); return ; }
GetNi(A, B, (n + 1) / 2); init(n);
memcpy(tA, A, n * 4); fill(tA + n, tA + N, 0);
NTT(tA, 1); NTT(B, 1);
for(reg int i = 0; i < N; i++) B[i] = 1LL * (2 - 1LL * tA[i] * B[i] % mod + mod) * B[i] % mod;
NTT(B, 0); fill(B + n, B + N, 0);
} // 将求得A的逆放在B中
```
#### 小结$1$
多项式求逆实际上是一个倍增的过程。
每一次确定的答案多项式就会增长一倍。
#### 练习$1$
[模板题](https://www.luogu.org/problemnew/show/P4238)
### 多项式求$ln$
#### 问题$2$描述
给定一个多项式$f(x)$，求出$g(x)$满足$g(x) \equiv ln\ f(x)\ (mod\ x^n)$。
#### 问题$2$分析
这个还是比较好推的。
我们对$g(x)$求个导，得到这样一个玩意：
$$g'(x) \equiv ln'(f(x)) \ast f'(x)\ (mod\ x^n)$$
$$g'(x) \equiv \frac{f'(x)}{f(x)}\ (mod\ x^n)$$
然后$\frac{1}{f(x)}$这个东西我们可以用多项式求逆搞出来，然后和$f'(x)$(这个东西很好算，用上面介绍的多项式求导的公式就好了)乘起来就好了。
我们搞出来了$g'(x)$，但是想要我们要知道的是$g(x)$啊。。
把导数还原成多项式。。这个用上面的那一个积分的公式就出来了。。
时间复杂度$O(nlogn)$
代码有点长啊。。还是只放上比上面的代码多出来的部分吧。。(这就清爽多了。。)
```
// 后面的内容就是在前面的基础上加的东西
inline void GetDao(reg int a[], reg int b[], reg int n) {
for(reg int i = 1; i < n; i++) b[i - 1] = 1LL * a[i] * i % mod; b[n - 1] = 0;
} // 将a求得的导数放在b中
inline void Getjf(reg int a[], reg int b[], reg int n) {
for(reg int i = 1; i < n; i++) b[i] = 1LL * a[i - 1] * quick_pow(i, mod - 2) % mod; b[0] = 0;
} // 将a积分出来的多项式放在b中
inline void Getln(reg int a[], reg int b[], reg int n) {
GetNi(a, b, n); GetDao(a, c, n); init(n); NTT(b, 1), NTT(c, 1);
for(reg int i = 0; i < N; i++) b[i] = 1LL * b[i] * c[i] % mod;
NTT(b, 0); Getjf(b, c, n); memcpy(b, c, n * 4);
} // 将ln(a)求得的多项式放在b中
```
#### 问题$2$小结
多项式求$ln$需要求一个导数，然后发现是两个比较好求的多项式的乘积，这样一来就比较可以简单计算了。
#### 练习$2$
[模板题](https://www.luogu.org/problemnew/show/P4725)
### 多项式复合
#### 问题$3$描述
给定一个多项式$G(x)$，求出一个多项式$f(x)$使得$G(f(x)) \equiv 0\ (mod\ x^n)$
#### 问题$3$分析
~~大量数学式来袭，请系上安全带，准备开车了~~
首先我们需要知道泰勒展开。
> 已知多项式$F(x)$，以及其在$x_0$的值，则该多项式在$x$的取值可表示为：
>
> $$F(x) = G(x_0) + \sum_{i=1}^{\infty}\frac{G^{(i)}(x_0)}{i!}(x-x_0)^i$$
>
> 其中$G^{(i)}(x_0)$表示对$G(x_0)$求$i$阶导数
那么这里有什么用呢。。
假设我们已经知道了一个多项式$f_{t-1}$使得$G(f_{t-1}) \equiv 0\ (mod\ x^{2^{t-1}})$，然后现在的问题是求一个多项式$f_t$使得$G(f_t) \equiv 0\ (mod\ x^{2^t})$
这样的话。。我们尝试对$G(f_t)$做个泰勒展开：
$$G(f_t) \equiv G(f_{t-1}) + \sum_{i=1}^{\infty}\frac{G^{(i)}(f_{t-1})}{i!} \ast (f_t-f_{t-1})^i\ (mod\ x^{2^t})$$
然后发现这个式子好像并不是很可做的样子啊。。
那么冷静分析一下，发现由于有：
$$G(f_{t}) \equiv 0\ (mod\ x^{2^{t}})$$
则说明$G(f_t)$除常数项外系数不为$0$的项次数大于$t$，那么我们就可以有：
$$G(f_{t}) \equiv 0\ (mod\ x^{2^{t-1}})$$
又因为：
$$G(f_{t-1}) \equiv 0\ (mod\ x^{2^{t-1}})$$
则可以得知：
$f_t-f_{t-1}$的前$2^{t-1}$项均为$0$，自然而然的，$(f_t-f_{t-1})^2$的前$2^t$项均为$0$...然后范围不断扩大。
然后回到上面的式子，发现是在模$x^{2^t}$的意义下。那么显然的是，包含了$(f_t-f_{t-1})^x\ (x > 1)$的项都为$0$了。
然后我们再把上面的式子化简一下，就可以得到：
$$G(f_t) \equiv G(f_{t-1}) + G'(f_{t-1}) \ast (f_t-f_{t-1})\ (mod\ x^{2^t})$$
简单多了。。
然后由我们要求的式子：
$$G(f_t) \equiv 0\ (mod\ x^{2^t})$$
所以有：
$$G(f_{t-1}) + G'(f_{t-1}) \ast (f_t-f_{t-1})\ \equiv 0\ (mod\ x^{2^t})$$
我们再变形一下：
$$f_t=f_{t-1}-\frac{G(f_{t-1})}{G'(f_{t-1})}$$
这样我们就得到了一个倍增的做法了。
复杂度$O(nlogn)$
#### 小结$3$
多项式复合需要使用泰勒展开公式。
套用泰勒展开公式的时候需要观察式子特征然后去掉没有用的项简化计算。
#### 练习$3$
尝试不看上面的内容重新推一下这个递推式。
### 多项式求$exp$
#### 问题$4$描述
给出一个多项式$F(x)$，求出$e^{F(x)}$。
#### 问题$4$分析
如果理解了上面的多项式复合的话，这个还是比较简单的。
我们可以构造一个多项式$G(g(x)) = ln(g(x)) - F(x)$，然后$G(g(x)) \equiv 0\ (mod\ x^n)$的解$g(x)$就满足$g(x) \equiv e^{F(x)}\ (mod\ x^n)$
多项式复合！！
套用一下上面的公式就好了。
> Tips：公式中的$G'(g(x))$是这样的：
>
> $$G'(g(x)) \equiv \frac{1}{g(x)} \ (mod\ x^n)$$
>
> 原因：这里的$g(x)$应看做一个字母！不要看做一个多项式！$F(x)$是一样的道理！
所以递推式长这个样子：
$$f_t \equiv f_{t-1} - (ln(f_{t-1})+F(x)) \ast f_{t-1} \ (mod\ x^{2^t})$$
然后照例倍增就好了。。
复杂度$O(nlogn)$
照例给出代码。注意带上$exp$的求$ln$还需要在后面加上清零，不然会$WA$。(调了一个小时的地方啊。。)
```
inline void Getln(reg int a[], reg int b[], reg int n) {
GetNi(a, b, n); GetDao(a, c, n); init(n); NTT(b, 1); NTT(c, 1);
for(reg int i = 0; i < N; i++) b[i] = 1LL * b[i] * c[i] % mod;
NTT(b, 0); Getjf(b, c, n); memcpy(b, c, n * 4); fill(c, c + N, 0); // 就是这里了。。暂时使用的c数组需要清零。这里因为知道用过的地方所以直接精准定位了。。
}
inline void Getexp(reg int a[], reg int b[], reg int n) {
if(n == 1) { b[0] = 1; return ; }
Getexp(a, b, (n + 1) >> 1); Getln(b, tB, n); init(n);
fill(tB + n, tB + N, 0); memcpy(tC, a, 4 * n); fill(tC + n, tC + N, 0);
NTT(b, 1), NTT(tB, 1), NTT(tC, 1);
for(reg int i = 0; i < N; i++) b[i] = (1LL * b[i] * (1LL - tB[i] + tC[i]) % mod + mod) % mod;
NTT(b, 0); fill(b + n, b + N, 0); fill(tB, tB + N, 0);
} // 将求得的a的exp放在b中。
```
#### 小结$4$
多项式求$exp$需要用到多项式复合和多项式求$ln$。
#### 练习$4$
1. [模板题](https://www.luogu.org/problemnew/show/P4726)
2. 尝试自己推一下多项式开根的递推式([多项式开根](https://www.luogu.org/problemnew/show/P5205))
### 多项式快速幂
#### 问题$5$描述
给定一个多项式$f(x)$，求一个多项式$g(x)$使得$g(x) \equiv f^k(x)\ (mod\ x^n)$。
#### 问题$5$分析
这个。。只要找到了一个突破口就好了。
首先联想一下：什么样的运算能够把指数变成四则运算呢？？
求对数啊！！
那么我们把两边都套上一个$ln$试试：
$$ln(g(x)) \equiv ln(f^k(x))\ (mod\ x^n)$$
$$ln(g(x)) \equiv k\times ln(f(x))\ (mod\ x^n)$$
这样就好了么。。
然后再把$g(x)$还原回来：
$$e^{ln(g(x))} \equiv e^{k\times ln(f(x))} \ (mod\ x^n)$$
$$g(x) \equiv e^{k\times ln(f(x))} \ (mod\ x^n)$$
大功告成！！
复杂度$O(nlogn)$
#### 小结$5$
多项式快速幂需要把指数给弄下来，这让我们联想到对数运算。
#### 练习$5$
好好理解和掌握上面的思想。尝试写一下多项式快速幂的代码。
### 多项式除法
#### 问题$6$描述
给定一个$n$次多项式$A(x)$和一个$m$次多项式$B(x)$，求出多项式$Q(x)$和$R(x)$，且满足以下条件：
1. $A(x) = B(x) \ast Q(x) + R(x)$
2. $Q(x)$的次数为$n-m$，$R(x)$的次数小于$m$
#### 问题$6$分析
这个的话。。有一个思路奇诡的巧妙做法：
> 定义$A^{r(n)}(x)$是一种对多项式次数$\le n$的多项式的操作：将次数从$0$到$n$的项的系数翻转。
>
> 公式表达：
>
> 若原多项式$A(x)$可表示为：(大于多项式的次数的项的$a_i=0$)
>
> $$A(x)=\sum_{i=0}^{n}a_ix^i$$
>
> 则$A^{r(n)}(x)$可表示为：
>
> $$A^{r(n)}(x)=\sum_{i=0}^{n}a_{n-i}x^i$$
然后我们就可以拿着这个东西搞事了。。
首先可以发现这样一个等式：
$$A^{r(n)}(x) = x^n \times A(\frac{1}{x})$$
然后由于$A(x) = B(x) \ast Q(x) + R(x)$，我们可以变一下形：
$$A(\frac{1}{x}) = B(\frac{1}{x}) \ast Q(\frac{1}{x}) + R(\frac{1}{x})$$
应该没有一点问题。。
然后带入上式可得：
$$A^{r(n)}(x) = x^n \times (B(\frac{1}{x}) \ast Q(\frac{1}{x}) + R(\frac{1}{x}))$$
$$A^{r(n)}(x) = x^n \times (B(\frac{1}{x}) \ast Q(\frac{1}{x})) + x^n \times R(\frac{1}{x})$$
$$A^{r(n)}(x) = (x^m \times (B(\frac{1}{x}) \ast (x^{n-m} \times Q(\frac{1}{x})) + x^n \times R(\frac{1}{x})$$
$$A^{r(n)}(x) = B^{r(m)}(x) \ast Q^{r(n-m)}(x) + R^{r(n)}(x)$$
然后由于$R(x)$的次数小于$m$，那么从第$n$项开始转的话$R^{r(n)}(x)$的前$n-m$项的系数就必然为$0$。
那么我们可以模一下$x^{n-m+1}$，这样的话$R^{r(n)}(x)$就没有了。。而且我们还完美地保留了$Q^{r(n-m)}(x)$
这样一来我们就可以得到下面这样的式子：
$$A^{r(n)}(x) \equiv B^{r(m)}(x) \ast Q^{r(n-m)}(x)\ (mod\ x^{n-m+1})$$
然后移一下项。。
$$Q^{r(n-m)}(x) \equiv \frac{A^{r(n)}(x)}{B^{r(m)}(x)}\ (mod\ x^{n-m+1})$$
然后我们把它转回去就好了。。
$$Q(x) \equiv (\frac{A^{r(n)}(x)}{B^{r(m)}(x)})^{r(n-m)}\ (mod\ x^{n-m+1})$$
至于$R(x)$。。用原来的$A(x) = B(x) \ast Q(x) + R(x)$移一下项然后直接算就好了。。
复杂度$O(nlogn)$
老规矩，上部分代码。
```
inline void Mul(reg int A[], reg int B[], reg int C[], reg int n, reg int m) {
init(n + m);
memcpy(tp, A, 4 * n), fill(tp + n, tp + N, 0); NTT(tp, 1);
memcpy(tq, B, 4 * m), fill(tq + m, tq + N, 0); NTT(tq, 1);
for(reg int i = 0; i < N; i++) C[i] = 1LL * tp[i] * tq[i] % mod; NTT(C, 0);
} // A(次数为n-1) * B(次数为m-1) 的结果放在C中
inline void Div(reg int A[], reg int B[], reg int Q[], reg int n, reg int m) {
memcpy(tB, B, 4 * (m + 1)); reverse(tB, tB + m + 1); GetNi(tB, Q, n - m + 1);
memset(tC, 0, 4 * MAXN); memcpy(tC, A, 4 * (n + 1)); reverse(tC, tC + n + 1);
Mul(Q, tC, Q, n - m + 1, n + 1); fill(Q + n - m + 1, Q + MAXN, 0); reverse(Q, Q + n - m + 1);
} // A(最高次为n) / B(最高次为m) 的结果放在Q中
inline void Mod(reg int A[], reg int B[], reg int Q[], reg int R[], reg int n, reg int m) {
Mul(B, Q, R, m + 1, n - m + 1); for(reg int i = 0; i <= n; i++) R[i] = (A[i] - R[i] + mod) % mod;
} // 计算除法后剩下的余项
```
#### 小结$6$
多项式除法用了一种比较骚的做法：把系数转过来。
#### 练习$6$
[模板题](https://www.luogu.org/problemnew/show/P4512)
## 完结撒花