多项式的表示
系数表示法
即\(F(x)=a_0x^0+a_1x^1+...+a_nx^n\)
点值表示法
一个\(n\)次多项式可以被\(n+1\)个点唯一确定
可以用这\(n+1\)个点表示该多项式
多项式卷积
\[(f*g)(x)=\sum_{i=0}^{n}\sum^n_{j=0}a_ib_{j}x^{i+j} \]说白了就是暴力展开
快速傅里叶变换（FFT）
单位根
对于复数\(\omega\)满足\(\omega^n=1\)，则称$\omega \(为\)n$次单位根
对应为复平面上平分单位圆的\(n\)个单位向量
可用复数的三角表示构成，也可用欧拉公式
性质
1、\(\omega^k_n=\omega^{2k}_{2n}\)
2、\(\omega^k_n=-\omega_n^{k+\frac n 2}\)
3、\(\omega^0_n=\omega^n_n=1\)
对应到复平面很好理解
DFT离散快速傅里叶变化
即把多项式用\(n\)次单位根转成点值表示法
对于多项式\(F(x)=a_0x^0+a_1x^1+...+a_{n-1}x^{n-1}\)，\(n\)为\(2^p\)
奇偶分项：\(F(x)=a_0x^0+a_2x^2+...+a_{n-2}x^{n-2}+x(a_1x^0+a_3x^2+...+a_{n-1}x^{n-2})\)
设多项式\(G(x)=a_0x^0+a_2x^1+...+a_{n-2}x^{\frac n 2-1},H(x)=a_1x^0+a_3x^1+...+a_{n-1}x^{\frac n 2-1}\)
则有\(F(x)=G(x^2)+x\cdot H(x^2)\)
设\(1\le k < \frac n 2\)，将单位根\(\omega^k_n\)和\(\omega^{k+\frac n 2}_n\)带入，则
\[F(\omega^k_n)=G((\omega^k_n)^2)+\omega^k_n\cdot H((\omega^k_n)^2) \]\[\hspace{0.3cm}=G(\omega^{2k}_n)+\omega^k_n\cdot H(\omega^{2k}_n) \]\[\hspace{0.3cm}=G(\omega^{k}_{\frac n 2})+\omega^k_n\cdot H(\omega^{k}_{\frac n 2}) \]\[F(\omega^{k+\frac n 2}_n)=G((\omega^{k+\frac n 2}_n)^2)+\omega^{k+\frac n 2}_n\cdot H((\omega^{k+\frac n 2}_n)^2) \]\[\hspace{0.6cm}=G(\omega^{2k+n}_n)+\omega^{k+\frac n 2}_n\cdot H(\omega^{2k+n}_n) \]\[=G(\omega^{k}_{\frac n 2})-\omega^k_n\cdot H(\omega^{k}_{\frac n 2})\hspace{0.45cm} \]对\(G,H\)递归求出各自的点值表示\((\omega^{1}_{\frac n 2},\omega^{2}_{\frac n 2},...,\omega^{\frac n 2-1}_{\frac n 2})\)，就可以\(O(n)\)得到\(F\)的点值表示
IDFT快速傅里叶逆变换
即把单位根全部取倒数跑一边DFT，得到每个数除以\(n\)，可得到新的多项式
迭代FFT
（待补充）
快速数论变换（NTT）
求\([x^i](f*g)(x)\ \bmod p\)
简单来说就是把单位根换成原根
原根的性质：
1、对于质数\(p\)的原根\(g\)，\(g^1,g^2,...g^{p-1}\)互不相同
2、单位根的三个性质都有
因此，可以进行模意义下的DFT和IDFT
原根的使用
类比单位根，我们可以认为\(g^1,g^2,...g^{p-1}\)这\(p-1\)个数把单位圆均分成\(p-1\)份，可以通过均等间隔选点来改变切割份数，也就是说，如果想用\(g^i\)代替\(\omega_n^k\)，就必须满足\(p-1\)为\(n\)的整数倍
\(998244353=7*17*2^{23}+1,g=3\)，\(2^{23}\)一般可以满足分治需求的份数
任意模数下NTT（MTT）
多项式的运算
多项式求逆
求多项式\(G(x)\)，使得\(F(x)*G(x)\equiv 1\pmod {x^n}\)
这里的模运算其实是砍掉\(x^n\)及以后的项
利用倍增求解：
设\(H(x)\)满足\(F(x)*H(x)\equiv 1\pmod {x^{\lceil\frac n 2\rceil}}\)
且易知\(F(x)*G(x)\equiv 1\pmod {x^{\lceil\frac n 2\rceil}}\)
则有\(F(x)*(G(x)-H(x))\equiv 0\pmod {x^{\lceil\frac n 2\rceil}}\)
\(G(x)-H(x)\equiv 0\pmod {x^{\lceil\frac n 2\rceil}}\)
\((G(x)-H(x))^2\equiv 0\pmod {x^{\lceil\frac n 2\rceil}}\)
\(G(x)^2-2G(x)H(x)+H(x)^2\equiv 0\pmod {x^{\lceil\frac n 2\rceil}}\)
\(G(x)^2-2G(x)H(x)+H(x)^2\equiv 0\pmod {x^n}\textcolor{red}{{}^*}\)
乘上\(F(x)\)，根据\(F(x)*G(x)\equiv 1\pmod {x^n}\)：
\(G(x)-2H(x)+F(x)H(x)^2\equiv 0\pmod {x^n}\)
\(G(x)\equiv 2H(x)-F(x)H(x)^2\pmod {x^n}\)
细节
注意生成\(G(x)=2H(x)-F(x)*H^2(x)\)时，要把\(G(x)\)的\(0\sim 2^p-1\)次项全部算出来（而不是只算前\(n\)项）
因为在系数-点值表示相互转换时，各项都是互相依赖的（唯一地表示一个多项式），只做一点会导致多项式不正确
多项式求ln
多项式求exp
多项式开根
生成函数
拉格朗日插值
定义
我们知道，\(n\)个点可以唯一确定一个\(n-1\)次多项式（如三点确定一个二次函数）
那么拉格朗日插值就是根据这个原理形成的多项式表示法
对于\(n\)个点\((x_1,y_1),(x_2,y_2),...,(x_n,y_n)\)，有
\[F(x)=\sum^n_{i=1} y_i\prod_{j=1}^{n,j\not=i}\frac{x-x_j}{x_i-x_j} \]利用该插值表示法，可以绕过求系数表示法，\(O(n^2)\)求出\(F(x)\)
编号连续的插值
若\(x_i=i\)，及\(x\)为\([1,n]\)，则有
\[F(x)=\sum^n_{i=1} y_i\prod_{j=1}^{n,j\not=i}\frac{x-j}{i-j} \]发现该式分子分母分别整合得到：
\[F(x)=\sum^n_{i=1} y_i\frac{\prod^n_{j=1}(x-j)}{(x-i)\cdot(-1)^{n-i}\cdot(i-1)!\cdot(n-i)!} \]通过预处理阶乘逆元\(facinv[]\)数组和\(\prod^n_{j=1}(x-j)\)，可以将时间复杂度降至\(O(nlogn)\)（再预处理\((x-i)^{-1}\)可以达到\(O(n)\)）
拉插优化DP
原理：\(n\)次多项式求前缀和后为\(n+1\)次多项式，即\(F_{n+1}(n)=[F_n(1),F_n(1)+F_n(2),\ ...\ ,\sum _{i=1}^nF_n(i),\ ...\ ]\)
（详见题解）
所以对于满足状态\(f[]\)为多项式的DP，可以通过拉插来求出多项式
The Sum of the k-th Powers
经典模型：
\(\sum_{i=1}^ni^k\)
差分发现为\(n\)次多项式，故答案为\(n+1\)次多项式，拉插即可
P3643 [APIO2016] 划艇
设\(f[i][j]\)为学校\(i\)派\(j\)艘划艇，列出方程：
\[f[i][j]=\begin{cases}\sum^i_{k=1}\sum^j_{l=1}f[k][l]\ \hspace{0.4cm},l\le j\le r \\ 0\hspace{3cm},\text{otherwise}\end{cases} \]前缀和：
\[f[i][j]=\begin{cases}\sum^j_{k=1}[i-1][k]\ \hspace{0.4cm},l\le j\le r \\ f[i-1][j]\hspace{1.18cm},\text{otherwise}\end{cases} \]由于\(i=1\)时，\(f[i][j]=1\)，为\(0\)次多项式，则\(f[i][j]\)也是多项式
又注意到\(l,r\)范围很大，考虑离散化
但是离散化之后，原数列被分成若干段，且每段状态不一（如\(f[1][]\)会有\(0/1\)），不能用一个多项式表示，但是每段状态是一样的，可以用一个多项式表示
于是引出分段多项式做法：每一段维护一个多项式，总时间复杂度\(O(n^3)\)
p.s. 题解普遍用的是组合数，可以试试
p.s.s. 拉插优化DP要注意常数优化
标签：frac,pmod,多项式,cdot,omega,equiv From： https://www.cnblogs.com/zhone-lb/p/18522200