多项式

我们可以定义一个\((\mod x^n)\)意义下的系数\((\mod p)\)意义下的多项式域。
下面的操作一般而言都在这个意义下进行。

多项式加法

直接加。

多项式减法

直接减。

多项式求相反数

直接取反。

多项式积分&求导

直接积分&求导。

多项式乘法

直接乘。
给定\(f(x)=\sum_{i=0}^{n-1}a_ix^i,g(x)=\sum_{i=0}^{m-1}b_ix^i\)，求\(h(x)=f(x)g(x)\)。
做法有可以进行浮点数运算的FFT和可以进行取模运算的NTT。

FFT

基本流程

DFT（系数表示法转点值表示法）\(\rightarrow\)直接相乘\(\rightarrow\)IDFT（点值表示法转系数表示法）。

DFT

我们现在假如你对\(A(x)=\sum_{i=0}^{n-1}a_ix^i\)进行DFT。其中\(n=2^t\)。
按下标的奇偶性分类并把右边提一个\(x\)出来。
\(A_0(x)=\sum_{i=0}^{\frac n2-1}a_{2i}x^i,A_1(x)=\sum_{i=0}^{\frac n2-1}a_{2i+1}x^i\)
那么\(A(x)=A_0(x^2)+xA_1(x^2)\)。
对于\(k<\frac n2\)，将\(w_n^k\)以及\(w_n^{k+\frac n2}\)分别代入\(A(x)\)。
\(A(w_n^k)=A_0(w_n^{2k})+w_n^kA_1(w_n^{2k})=A_0(w_{\frac n2}^k)+w_n^kA_1(w_{\frac n2}^k)\)
\(A(w_n^{k+\frac n2})=A_0(w_{\frac n2}^k)-w_n^kA_1(w_{\frac n2}^k)\)
发现只有后面一项的符号不同，所以我们可以分治处理。

迭代求法

手玩以后发现每个位置分治后的位置就是其原本位置二进制反转后的结果。
所以我们可以先把原序列先变换成分治后的序列，然后一层层向上合并。
预处理\(i\)的二进制翻转\(rev[i]\)，如果\(i<rev[i]\)就交换序列元素。

IDFT

把DFT中\(A_1(x)\)前面的系数由\(w_n^k\)变为\(\overline{w_n^k}\)即可。

NTT

DFT

用\(g^\frac{P-1}n\)来代替\(w_n\)。
必须满足\(P=r\cdot2^k+1\)。这样的\(P\)称为费马素数。
一般是\(P=998244353,g=3\)。

IDFT

用\(a^{-1}\)代替\(\overline{a}\)。
（因为\(w_n^k=1\)，所以单位根的共轭实质上就是求逆）

多项式

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12093995.html