【学习笔记】多项式入门
前言
兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有多项式不会，不会就是不会，怎么学都不会......
本笔记用于记录简单多项式知识，供 $\texttt{CXY07}$ 脑抽时查看......
正题
多数模板会给提交记录传送门，或者贴板子。
多项式乘法
这个应该不会忘，贴板子算了
$\text{FFT}$ 传送
inline void FFT(cp *A,int opt) {
for(register int i = 0;i < lim; ++i)
if(i < r[i]) swap(A[i],A[r[i]]);
for(register int mid = 1;mid < lim; mid <<= 1) {
cp tmp = cp(cos(PI / mid),opt * sin(PI / mid));
for(register int j = 0;j < lim; j += (mid << 1)) {
cp now = cp(1,0);
for(register int k = 0;k < mid; ++k,now = now * tmp) {
cp x = A[j + k],y = now * A[j + mid + k];
A[j + k] = x + y;
A[j + k + mid] = x - y;
}
}
}
}
$\text{NTT}$ 传送
void NTT(int *A,int opt) {
for(int i = 0; i < lim; ++i)
if(rev[i] > i) swap(A[i],A[rev[i]]);
for(int mid = 1,w;mid < lim; mid <<= 1) {
w = qpow(opt == 1 ? G : Gi,(mod - 1) / (mid << 1));
for(int i = 0,now,x,y;i < lim;i += (mid << 1)) {
now = 1;
for(int j = 0;j < mid; j++,(now *= w) %= mod) {
x = A[i + j],y = (A[i + j + mid] * now) % mod;
A[i + j] = (x + y) % mod;
A[i + j + mid] = ((x - y) % mod + mod) % mod;
}
}
}
if(opt == -1) {
int ilim = inv(lim);
for(int i = 0;i < lim; ++i) A[i] = A[i] * ilim % mod;
}
}时间复杂度 $\mathcal{O}(n\log n)$。
多项式乘法逆
已知 $F(x)$，求 $G(x)$ 满足 $F(x)\times G(x)\equiv 1\ (\bmod\ x^n)$。
系数对 $998244353$ 取模。
假设已经求出 $G_0(x)$，使得 $F(x)\times G_0(x)\equiv 1\ (\bmod\ x^{\lceil \frac{n}{2} \rceil})$。
又 $F(x)\times G(x)\equiv 1\ (\bmod\ x^n)$。那么有：
$$F(x)\times (G_0(x)-G(x))\equiv 0\ (\bmod\ x^{\lceil \frac{n}{2} \rceil})$$
把 $F(x)$ 丢掉可得：
$$G_0(x)-G(x)\equiv 0\ (\bmod\ x^{\lceil \frac{n}{2} \rceil})$$
平方：
$$(G_0(x)-G(x))^2\equiv 0\ (\bmod\ x^n)$$
拆掉左边的平方：
$$G_0(x)^2-2G(x)\times G_0(x) + G(x)^2\equiv 0\ (\bmod\ x^n)$$
把 $F(x)$ 乘回来，由 $F(x)\times G(x)\equiv 1\ (\bmod\ x^n)$ 化简可得：
$$F(x)\times G_0(x)^2 - 2G_0(x) + G(x) \equiv 0\ (\bmod\ x^n)$$
挪一下：
$$G(x)\equiv G_0(x)\times (2-F(x)\times G_0(x))\ (\bmod\ x^n)$$
$\text{NTT}$ 即可。
时间复杂度 $\mathcal{O}(n\log n)$。
多项式 $\ln$
已知 $F(x)$，求 $G(x)$ 使得 $\ln F(x)\equiv G(x)\ (\bmod\ x^n)$。
即有：
$$G(x)\equiv \ln(F(x))\ (\bmod\ x^n)$$
考虑两边求导，复合函数求导公式是 $f(g(x))'=f'(g(x))\times g'(x)$，可得：
$$G'(x)\equiv \ln'(F(x))\times F'(x)\ (\bmod\ x^n)$$
考虑到 $\ln'(x)=\dfrac{1}{x}$，那么可以写成：
$$G'(x)\equiv \dfrac{F'(x)}{F(x)}\ (\bmod\ x^n)$$
右面做一次求导和一次求逆，然后乘起来即可。
现在得到了 $G'(x)$，再积分回来就能得到答案。
丢出求导、积分柿子：
$${x^{n}}'=nx^{n-1},\int\ x^n=\dfrac{1}{n+1}\ x^{n+1}$$
时间复杂度 $\mathcal{O}(n\log n)$。
多项式牛顿迭代
已知 $G(x)$，求 $F(x)$ 使得 $G(F(x))\equiv 0\ (\bmod\ x^n)$。
迭代解决，假设已经得到 $F_0(x)$ 使得：
$$G(F_0(x))\equiv 0\ (\bmod\ x^{\lceil \frac{n}{2} \rceil})$$
将 $G$ 在 $F(x)=F_0(x)$ 处展开，有：
$$G(F(x)) = \sum_{i=0}^{\infty} \dfrac{G^i(F_0(x))}{i!}(F(x)-F_0(x))^i$$
其中 $G^i$ 是 $G$ 的 $i$ 阶导函数。
由于 $F(x)-F_0(x)$ 后，次数低的一半的系数都是 $0$，若 $i\ge 2$ 则任意系数都会被模掉。因此取前 $2$ 项，可得：
$$G(F(x)) \equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\ (\bmod\ x^n)$$
又知道 $G(F(x))\equiv 0\ (\bmod\ x^n)$，所以：
$$F(x)\equiv F_0(x)-\dfrac{G(F_0(x))}{G'(F_0(x))}\ (\bmod\ x^n)$$
多项式 $\exp$
已知 $F(x)$，求 $G(x)$ 使得 $G(x)\equiv e^{F(x)}\ (\bmod\ x^n)$。
两边 $\ln$ 可得：
$$\ln G(x)-F(x)\equiv 0\ (\bmod\ x^n)$$
发现在求零点，所以考虑多项式牛顿迭代。
设 $f(G(x))=\ln G(x)-F(x)$，可以把 $G(x)$ 看做自变量，$F(x)$ 看做一个常数。
然后有：
$$f'(G(x))=\dfrac{1}{G(x)}$$
所以：
$$G(x)\equiv G_0(x)-\dfrac{f(G_0(x))}{\dfrac{1}{G_0(x)}}\ (\bmod\ x^n)$$
$$G(x)\equiv G_0(x)-f(G_0(x))G_0(x)\ (\bmod\ x^n)$$
$$G(x)\equiv G_0(x)(1-\ln G_0(x)+F(x))\ (\bmod\ x^n)$$
时间复杂度 $\mathcal{O}(n\log n)$。常数一个log
多项式开根
已知 $F(x)$，求 $G(x)$ 使得 $G^2(x)\equiv F(x)\ (\bmod\ x^n)$。
移项可得：
$G^2(x)-F(x)\equiv 0\ (\bmod\ x^n)$
又在找零点，直接多项式牛顿迭代。设 $f(G(x))=G^2(x)-F(x)$，有：
$$G(x)\equiv G_0(x)-\dfrac{f(G_0(x))}{f'(G_0(x))}\ (\bmod\ x^n)$$
又 $f'(G_0(x))=2G(x)$，化简可得：
$$G(x)\equiv \dfrac{G_0^2(x)+F(x)}{2G_0(x)}\ (\bmod\ x^n)$$
直接迭代求解。
需要注意的是迭代到长度为 $1$ 时，若 $F(0)=1$，则 $G(0)=1$，否则需要做二次剩余。
时间复杂度 $\mathcal{O}(n\log n)$。
分治 $\text{FFT}$
给定 $g_{1...n-1}$，求序列 $f_{0...n-1}$。
其中 $f_i=\sum_{j=1}^i f_{i-j}g(j)$，边界 $f_0=1$。
可以考虑类似 $\texttt{CDQ}$ 分治的思想，先递归处理左半边，然后更新对右半边的贡献。
其实就是先递归处理左边，然后把左边 $f$ 所得到的多项式和 $g$ 卷一下，然后就可以算出左边的 $f$ 对右边 $f$ 的贡献。
可以先把序列长度补到 $2$ 的整次幂，然后就可以每次平均分成两边处理了。
就这样随便口胡一下吧
多项式快速幂
给定 $n-1$ 次多项式 $A(x)$，求在 $\bmod\ x^n$ 的意义下的多项式 $B(x)$，使得 $A^k(x)\equiv B(x)\pmod {x^n}$，系数在 $\bmod\ 998244353$ 意义下进行运算。
对于 $[x^0]A=1$ 的情形，可以直接使用多项式 $\ln,\exp$ 解决。
$$B(x)\equiv A^k(x)\pmod {x^n}$$
$$\ln B(x)\equiv k\ln A(x)\pmod {x^n}$$
$$B(x)\equiv e^{k\ln A(x)}\pmod {x^n}$$
若 $[x^0]A\ne 0$ 且 $[x^0]A\ne 1$，可以先每一项除去 $[x^0]A$，最后乘上这个数字的次幂。
若 $[x^0]A=0$，那么就往后推，直到找到第一个非 $0$ 的位置，然后做上述操作。最后在多项式末尾补上原 $0$ 个数那么多倍的 $0$ 即可。注意什么时候对 $\text{mod}$ 取模，什么时候对 $\varphi(\text{mod})$ 取模。
时间复杂度 $\mathcal{O}(n\log n)$。
多项式除法
给定 $n$ 次多项式 $F(x)$ 和 $m$ 次多项式 $G(x)(n> m)$，求 $Q(x),R(x)$ 满足 $F(x)=Q(x)G(x)+R(x)$
运算在模 $998244353$ 意义下进行。
多项式带余除法。
考虑对于 $n$ 次多项式 $F(x)$，令 $F_R(x)=x^nF(\frac{1}{x})$。即将系数 $\text{reverse}$。
那么有：