多项式学习笔记
Nemlit
2019-10-07 20:52:04
## $\rm FFT$
首先我们要求的柿子长这样：
$$c(k) = \sum_{i+j = k}a(i)\times b(j)$$
大概思路：先把两个多项式转成点值$(DFT)$，再把两个多项式的点值乘在一起，把新的点值转成多项式$(IDFT)$即可
## $\rm DFT:$
首先要了解复数的运算
$$(a + b\times i) +(c+d\times i) = (a+c)+(b+d)\times i$$
$$(a + b\times i) -(c+d\times i) = (a-c)+(b-d)\times i$$
$$(a + b\times i) \times (c+d\times i) = (a\times c - b\times d)+(a\times d+b\times d)\times i$$
随便说下单位圆/单位根：
现在我们要把圆平分成$n$个，每一个的大小应该是$cos(2 Π /n), sin(2Π / n)$
步入正题，具体操作长这样：
$$F(x) = a_0\times x^0+a_1\times x^1+a_2\times x^2+……+a_n\times x^n$$
设$F1(x) = a_0\times x^0+a_2\times x^1+……+a_{n}\times x^{\frac{n}{2}}$，$F2(x) = a_1\times x^0+a_3\times x^1+……+a_{n - 1}\times x^{\frac{n}{2}}$
$$F(x) = F1(x^2)+x\times F2(x^2)$$
现在我们只需要知道$F1(x), F2(x)$就可以知道$F(x)$了，于是我们可以递归处理（所以我们需要保证多项式的项数为$2^x$）
把单位根带到上述式子里面去，我们有：
$$F(w_n^x) = F1(w_n^{2\times x})+w_n^x\times F2(w_n^{2\times x})$$
现在我们需要单位根的第一条性质（带到单位圆上就知道了）：
$$w_{2n}^{2x} = w_{n}^x$$
顺便介绍性质二（还是画画图就知道了）：
$$w_{n}^{x+\frac{n}{2}} = -w_{n}^x$$
通过性质一，我们可以把柿子化成：
$$F(w_n^x) = F1(w_{\frac{n}{2}}^{x})+w_n^x\times F2(w_{\frac{n}{2}}^{x})$$
由于我们只知道$F1(x), F2(x)$的$0-\frac{n}{2}$的所有点值要求出$F(x)$的$0-n$的所有点值
分类讨论一下：
如果$x<\frac{n}{2}$，直接用$F1,F2$的值就行
如果$x≥\frac{n}{2}$，不妨设$x=x+\frac{n}{2}$
$$F(w_n^{x+\frac{n}{2}}) = F1((w_{n}^{x+\frac{n}{2}})^2)+w_n^{x+\frac{n}{2}}\times F2((w_{n}^{{x+\frac{n}{2}}})^2)$$
由于第二条性质
$$F(w_n^{x+\frac{n}{2}}) = F1((-w_{n}^x)^2)-w_n^{x}\times F2((-w_{n}^{x})^2)$$
$$F(w_n^x) = F1(w_{\frac{n}{2}}^{x})-w_n^x\times F2(w_{\frac{n}{2}}^{x})$$
发现只有一个符号的区别
## $\rm IDFT$
我们假设我们通过$DFT$求出了点值为$a_0, a_1……, a_n$，最后我们要求出的值为$A_0, A_1……, A_n$
其实我们只要解一个这样的方程组：
$$A_0\times (w_n^0)^0+A_1\times (w_n^0)^1+A_2\times (w_n^0)^2+……+A_n\times (w_n^0)^{n}$$
$$A_0\times (w_n^1)^0+A_1\times (w_n^1)^1+A_2\times (w_n^1)^2+……+A_n\times (w_n^1)^{n}$$
$$……$$
$$A_0\times (w_n^{n - 1})^0+A_1\times (w_n^{n - 1})^1+A_2\times (w_n^{n - 1})^2+……+A_n\times (w_n^{n - 1})^{n}$$
这就是一个矩阵形式了
第一个矩阵是所有的$(w_n^x)^k$，我们计为矩阵V，第二个矩阵为所有的$A_x$计为A，第三个矩阵为所有的$a_x$计为a
于是我们的柿子变成了$A\times V=a$
如果我们知道$V^{-1}$，那么我们有$a\times V^{-1} = A$，a即为所求
现在考虑求逆：
我们需要介绍性质三：$\sum_{j = 0}^{n - 1}(w_n^k)^j=[k==0]\times n$
证明其实不难，~~画画图就好了~~，我们要求的柿子为：$\sum_{j = 0}^{n - 1}(w_n^k)^j$
如果$k =0$，那么原式$=\sum_{j = 0}^{n - 1} = n$
如果$k≠0$，记$s=\sum_{j =0}^{n - 1}(w_n^k)^j$
$s\times w_n^k = \sum_{j=1}^{n}(w_n^k)^j =s-1+(w_n^k)^n = s$
因为$w_n^k≠0$,所以$s=0$
我们令$V^{-1}(i, j) = (w_n^{-i})^j$
所以$(V\times V^{-1})(i, j)=\sum_{k =0}^{n-1}(w_n^{-i})^k\times (w_n^k)^j=\sum_{k = 0}^{n - 1}(w_n^{j -i})^k$
根据性质三，当$i=j$时$(V\times V^{-1})(i, i)=n$，否则$=0$，只需要把每一项$/n$即可
然后我们有发现，只需要把$A$看成新的系数，把所有的$(w_n^j)^k$看成$(w_n^{-j})^k$，那么就是一边新的$DFT$了
所以唯一的差别就是单位根前面乘了一个$-1$即可
## $\rm Code:$
```cpp
struct node {
D x, y;
}a[maxn], b[maxn];
il node operator + (node a, node b) {return (node){a.x + b.x, a.y + b.y};}
il node operator - (node a, node b) {return (node){a.x - b.x, a.y - b.y};}
il node operator * (node a, node b) {return (node){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};}
int n, m, lim;
il void FFT(node *x, int f, int len) {
if(len == 1) return;
node f1[len >> 1], f2[len >> 1];
for(re int i = 0; i < len; i += 2) f1[i / 2] = x[i], f2[i / 2] = x[i + 1];
FFT(f1, f, len >> 1), FFT(f2, f, len >> 1);
node w = (node){1, 0}, base = (node){cos(2.0 * pi / len), f * sin(2.0 * pi / len)};
for(re int i = 0; i < (len >> 1); ++ i, w = w * base) {
x[i] = f1[i] + w * f2[i], x[i + (len >> 1)] = f1[i] - w * f2[i];
}
}
int main() {
n = read(), m = read();
rep(i, 0, n) a[i].x = read();
rep(i, 0, m) b[i].x = read();
while((1 << lim) <= n + m) ++ lim;
FFT(a, 1, (1 << lim)), FFT(b, 1, (1 << lim));
rep(i, 0, (1 << lim)) a[i] = a[i] * b[i];
FFT(a, -1, (1 << lim));
rep(i, 0, n + m) printf("%d ", (int)(a[i].x / (1 << lim) + 0.5));
return 0;
}
```
讲讲迭代版的$\rm FFT$
通过打表发现：一个数x再最后一次出现的位置$r[i]$是可以通过公式算出来的：$r[i] = (r[i >> 1] >> 1)\ |\ ((i\ \&\ 1) << (lim - 1))$
然后我们在$\rm FFT$前面把x交换到对应位置，然后用类似上述方法一个个合并即可~~（我不是懒，是怕东西太多页面卡）~~
## $\rm Code:$
```cpp
il void FFT(node *x, int f, int len) {
rep(i, 0, len - 1) if(i < r[i]) swap(x[i], x[r[i]]);
for(int mid = 1; mid < len; mid <<= 1) {
node base = (node){cos(pi / mid), f * sin(pi / mid)};
for(re int p = mid * 2, j = 0; j < len; j += p) {
node w = (node){1, 0};
for(re int k = 0; k < mid; ++ k, w = w * base) {
node a = x[j + k], b = w * x[j + k + mid];
x[j + k] = a + b, x[j + k + mid] = a - b;
}
}
}
}
rep(i, 0, (1 << lim)) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));
```
## $\rm NTT:$
大概就是你把原根看成单位根，然后跑$FFT$即可~~（我不是懒，是怕东西太多页面卡）~~
## $\rm Code:$
```cpp
#define mod 998244353
#define invG 332748118
#define G 3
#define maxn 10000006
int n, m, a[maxn], b[maxn], l, lim = 1, r[maxn];
il int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = 1ll * r * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return r;
}
il void NTT(int *x, int f, int len) {
rep(i, 0, len) if(i < r[i]) swap(x[i], x[r[i]]);
for(re int mid = 1; mid < len; mid <<= 1) {
int base = qpow((f == 1) ? G : invG, (mod - 1) / (mid << 1));
for(re int p = mid * 2, j = 0; j < len; j += p) {
for(re int k = 0, w = 1; k < mid; ++ k, w = 1ll * w * base % mod) {
int a = x[j + k], b = 1ll * w * x[j + k + mid] % mod;
x[j + k] = (a + b) % mod, x[j + k + mid] = (a - b + mod) % mod;
}
}
}
}
signed main() {
n = read(), m = read();
rep(i, 0, n) a[i] = read();
rep(i, 0, m) b[i] = read();
while(lim <= (n + m)) ++ l, lim <<= 1;
rep(i, 0, lim) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
NTT(a, 1, lim), NTT(b, 1, lim);
rep(i, 0, lim) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, -1, lim);
int inv = qpow(lim, mod - 2);
rep(i, 0, n + m) printf("%d ", (1ll * a[i] * inv) % mod);
return 0;
}
```
### $\rm MTT$
$\rm MTT$又叫拆系数$\rm FFT$，把多项式拆分成$A\times M + B$的形式。（其中表示点值）
然后我们有两个多项式，假设第一个在$/M$意义下算出来的多项式为$A_1$，再$\%M$意义下算出来的多项式为$B_1$，第二个多项式的值分别为$A_2, B_2$。然后我们本质上就是要计算$(A_1\times M + B_1)\times (A_2\times M + B_2)$
我们拆系数的原因是因为不去摸的话算出来的值很大，$\rm FFT$的精度会炸掉。假设我们选择的$M$为$\sqrt{P}$，那么最后的结果会变成$P$级别。保证了精度
$(A_1\times M + B_1)\times (A_2\times M + B_2)=A_1\times A_2\times M^2+(A_1\times B_2 + A_2\times B_1)\times M + B_1 \times B_2$
我们分别算出$A_1\times A_2, A_1\times B_2 + A_2\times B_1, B_1 \times B_2$，再讲答案合并即可
模板题有点卡精度，需要$long\ double$
### $\rm FWT$
咕咕咕
### 多项式求逆
首先假设原函数为$G$，$G\times F=1(mod\ x^n)$，我们有$F\%x^1=inv(G_0)$，然后，我们思考怎么从$F\%x^{\frac{n}{2}}$推出$F\%x^n$
令新的多项式为$H$，我们已知$F\times G=1(mod\ x^\frac{n}{2}),H\times G=1(mod\ x^n)$我们不难发现：$H-F=0(mod\ x^\frac{n}{2})$，所以我们有$(H-F)^2=0(mod\ x^n)$（这个证明可以把$(H-F)\%x^\frac{n}{2}$为一个$0-\frac{n}{2}$项全为0的多项式，发现平方后前N项全是0）展开后我们有：$H^2+F^2-2\times H\times F=0(mod\ x^n)$，两边同时乘以$G$得，$H+F^2G-2\times F=0(mod\ x^n)$
### 分治$\rm FFT$
#### 法一：直接用求逆来做：
构造$F(x)=\sum_{i=0}^{\infty}x^if_i,\;\;G(x)=\sum_{i=0}^{\infty}x^ig_i$
$F(x)\times G(x)=\sum_{i=0}^{inf}x^i\sum_{j=0}^{i}f_{i-j}g_j=\sum_{i=1}^{inf}x^if_i=F(x)-1$（当$i=0$时$g_i=0$）
所以我们有：$F(x)\times G(x)+1=F(x)$
$F(x)=\dfrac{1}{1-G(x)}$，求逆即可
#### 法二：正宗分治$\rm FFT$
我们把多项式拆成两个部分，$[l, mid],[mid + 1, r]$，分别递归求解，然后再合并答案。
考虑第一部分对第二部分的贡献，也就是对于每一个$x\in [l, r]$, $w[x]=\sum_{i=l}^{mid}f_i\times g_{x-i}$
化简一下（这里我们令$f_x=0, x\in[mid + 1, r]$），我们有$w[x]=\sum_{i =0}^{x-l-1}f_{i+l}\times g_{x-i-l}$
于是，令$a_i=f_{i+l}, b_i=g_{i+1}$。$w[x]=\sum_{i =0}^{x-l-1}a_{i}\times b_{x-i-l-1}$，不难发现这是一个卷积的形式，算出来即可。
### 求导与泰勒展开
详见博文[[THUWC2017]在美妙的数学王国中畅游](https://www.luogu.com.cn/blog/tbr-blog/solution-p4546)
### 牛顿迭代
牛顿迭代的一般运用是求出函数$G(F(x))$的零点
假设我们已经知道了$G(F_0(x))=0(mod\ x^{\frac{n}{2}})$，$F(x)-F_0(x)=0(mod\ x^{\frac{n}{2}})$
将其在$F_0(x)$处泰勒展开，我们有$G(F(x))=G(F_0(x))+\dfrac{G'(F_0(x))}{1!}\times (F(x)-F_0(x))+\dfrac{G''(F_0(x))}{2!}\times (F(x)-F_0(x))^2+……$
由于我们只需要拓展成$mod\ x^n$，二次项以后，最小非零项大于n，所以我们都可以忽略
带入$G(F_0(x))$，移项，两边同时除以$G'(F_0(x))$
$F(x)=F_0(x) - \dfrac{G(F_0(x))}{G'(F_0(x))}$
### 多项式求$\rm ln$
$B(x)=ln(A(x))$，所以有：$B(x)'=ln(A(x))'\times A(x)'$
$B(x)'=\dfrac{A(x)'}{A(x)}$，所以我们可以通过求逆和求导计算出$B(x)'$，然后再通过求导逆运算积分求出$B(x)$即可
### 多项式求$\rm exp$
由于$e^{B(x)}=A(x)$，两边同时取$ln$，并且移项后我们有：
$ln(A(x))-B(x)=0$
然后看作$G(A(x))=ln(A(x))-B(x)$，求这个函数的0点。
由于我们要求的是$A(x)$，$B(x)$的变化与$A(x)$无关，可以看成一个常数，然后把$B(x)$看作常量，把$A(x)$看作变量，我们有$G'(A(x))=\dfrac{1}{A(x)}$
带入牛顿迭代的柿子，我们有：$A(x)=A_0(x) - A_0(x)\times G(A_0(x))=A_0(x) - A_0(x)\times (ln(A_0(x))-B(x))$
$A(x)=A_0(x)\times (1 - ln(A_0(x))+B(x))$，于是我们每一步对其取$\rm ln$，做一遍多项式乘法即可
### 多项式除法
定义$F^R(x)$将$F(x)$系数反转后得到的多项式
$$F(x)=Q(x)\times G(x)+R(x)$$
$$F(\frac{1}{x})=Q(\frac{1}{x})\times G(\frac{1}{x})+R(\frac{1}{x})$$
同时乘以$x^n$
$$x^nF(\frac{1}{x})=x^{n-m}Q(\frac{1}{x})\times x^mG(\frac{1}{x})+x^{n-m-1}\times x^{m-1}R(\frac{1}{x})$$
$$F^R(x)=Q^R(x)\times G^R(x)+x^{n-m-1}R^R(x)$$
$$F^R(x)=Q^R(x)\times G^R(x)(mod\ x^{n-m-1})$$
所以根据多项式求逆可以求出$Q^R(x)$，再根据$R^R(x)=F^R(x)-Q^R(x)\times G^R(x)$即可求出$R(x)$
### 多项式开根
~~ln 以下再 exp 一下~~
$$H(x)^2=F(x)(mod\ x^{\frac{n}{2}})$$
$$G(x)^2=F(x)(mod\ x^{\frac{n}{2}})$$
$$G(x)-H(x)=0(mod\ x^{\frac{n}{2}})$$
$$G(x)^2-2\times H(x)G(x)+H(x)^2=0(mod\ x^{n})$$
$$F(x)+H(x)^2=2\times H(x)G(x)(mod\ x^{n})$$
$$\frac{F(x)}{2H(x)}+\frac{H(x)}{2}=G(x)(mod\ x^{n})$$
求逆即可。复杂度证明和求逆一样，都是一个$log$
### 多项式快速幂
$ln$ 以下再 $exp$ 一下（比倍增快速幂少了一个$log$）
### 插值
咕咕咕
### 一些简单的生成函数
#### 广义组合数：
$\dbinom{a}{i}=\dfrac{a^{\underline{i}}}{i!}$，所以组合数我们可以拓展到任意实数的情况
#### 广义二项式定理及其推论
$$(x+y)^{n}=\sum_{i=0}^{inf}\binom{n}{i}\times x^i\times y^{n-i}$$
$$(1+x)^{-a}=\sum_{i=0}^{\infty}\dbinom{-a}{i}x^i$$
$$\dbinom{-a}{i}=\dfrac{(-a)(-a-1)(-a-2)...(-a-i+1)}{i!}=(-1)^i\dfrac{(a+i-1)^{\underline{i}}}{i!}$$
所以：
$$(1+x)^{-a}=\sum_{i=0}^{\infty}(-1)^i\dbinom{a+i-1}{i}x^i$$
我们令$x=-x$代入上式：
$$(1-x)^{-a}=\sum_{i=0}^{\infty}(-1)^i\dbinom{a+i-1}{i}(-x)^i$$
即：
$$\dfrac{1}{(1-x)^n}=\sum_{i=0}^{\infty}\dbinom{n+i-1}{i}x^i$$
### 多项式三角函数
根据欧拉公式，我们有：$e^{ix}=cos(x)+i\times sin(x)$
$e^{iA(x)}=cos(A(x))+i\times sin(A(x))$
$e^{-iA(x)}=cos(A(x))-i\times sin(A(x))$
于是我们有：$cos(A(x))=\dfrac{e^{ix}+e^{-ix}}{2}, sin(A(x))=\dfrac{e^{ix}+e^{-ix}}{2\times i}$
发现仍然有虚数单位$i$，但是因为我们知道$i^2=-1$，于是二次剩余算一下即可