先贴个tp(其实是自己不会
呜噜噜多项式普及
呜噜噜多项式提高
关于多项式
它一般以这样的形态出现
$$
A(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n
$$
其中 $x$ 被称作自变量(?)，对应的每个 $a_0,a_1,a_2\cdots$称为这个多项式的系数，对于这个多项式的最高次数 $n$，我们称之为这个多项式的 度degree。
对于每个题目而言，我们知道的同时需要操作的一般也就是它的系数和它的度
多项式加减乘除！
为什么没有除呢？因为我还不会(现在我会啦!。两个多项式的加减即对应项系数的加减，我们可以 $O(n)$ 简单秒掉，但是多项式相乘呢?
这里我们引入一个新的概念(至少我是从这里才知道的)—— 卷积
形如$c_i=\sum_{j=0}^{i}{a_j\times b_{i-j}}$ 中的 $c_i$ 我们称之为 $a,b$ 两个数组的卷积
那么两个多项式相乘，实际上就是求两个多项式的卷积即$c_ix^i=\sum_{j=0}^{i}{a_jx^j\times b_{i-j}x^{i-j}}$，同时原本度都为为 $n$ 的两个多项式相乘后得到的多项式的度也就变成了 $2n$ .
快速傅里叶变换(FFT)
通过定义式，我们知道两个多项式相乘的复杂度是 $O(n^2)$ 级别的，这对于大多数的题目而言都太慢了，所以我们需要更优秀的算法，多项式的快速变换也就应运而生
对于一个多项式，我们不仅有系数表达(就是以上所用的表达)，还有点值表达
就好像 $n+1$ 个点就可以确定一个次数为 $n$ 的函数图像一样，一个度为 $n$ 多项式也可以转化为 $n+1$ 个点值
如何转换
首先我们又得引入几个新的概念：
复数
我们一般接触的数都属于实数范围，但还有一些不合法，但是依然存在的数，形如$\sqrt {-1}$(在下文中，我们称之为 $i$ )，我们称之为虚数.
而复数则是既含有实数，有含有虚数的数。一般来说，我们称复数的实数部分为实部，虚数部分的系数为虚部
复数之间的运算也同我们熟知的实数一样
单位复数根
我们设度为$n$ 的多项式的单位复数根为$ \omega_n =e^{2\pi i/n}=\cos(2\pi/n)+i\sin(2\pi/n)$
它有着非常好的性质
$\omega_n^n=1$
$\omega_{2n}^{2d}=\omega_n^d$
$\omega_{2n}^{d+n}=-\omega_{2n}^d$
$\sum_{k=1}^{n}w_n^k=0$
证明: $\sum_{k=1}^{n}\omega_n^k=\frac{\omega_n(\omega_n^n-1)}{\omega_n-1}=0$
离散傅里叶变换(DFT)
即将一个多项式转换为用表达单位复数根的形式，即
$$
y_k=A(\omega_n^k)=\sum_{j=0}^na_j\omega_n^{kj}
$$
两个多项式转换为点值表达之后，我们就可以$O(n)$对两个式子相乘
离散傅里叶逆变换(DFT)
这里本来有一个通过矩阵解释的绝妙的证明过程，但矩阵在Markdown中实在太难打了，所以很遗憾
$$
a_k=\sum_{j=0}^ny_j\omega_n^{-kj}
$$
这样我们就完成了多项式$O(n\log n)$相乘
具体实现代码
inline void Dft(comp *a,int len,int rev)
{
if(len==1)return;
for(register int i=0;i < len;++i)temp[i]=a[i];
for(register int i=0;i<len;++i)
if(i&1)
a[len/2+i/2]=temp[i];
else
a[i/2]=temp[i];
comp *g=a,*h=a+len/2;
Dft(g,len/2,rev),Dft(h,len/2,rev);
comp w(1,0),step(cos(2.0*pi/len),rev*sin(2.0*pi/len));
for(register int k=0;k<len/2;++k)
{
comp t=w*h[k];
temp[k]=g[k]+t;
temp[k+len/2]=g[k]-t;
w*=step;
}
for(register int i=0;i<len;++i)a[i]=temp[i];
}其中FFT有一个叫做蝴蝶变换的优化，大致即为将递归到最后一层时的得到的新数组序列预先处理好，就是将原数组排序为递归时得到的数组，再一层一层往上更新即可
inline void change(comp *a,int len)
{
for(register int i=0;i<len;++i)
{
re[i]=re[i>>1]>>1;
if(i&1)
re[i]|=len>>1;
}
for(register int i=0;i<len;++FFTi)
if(i<re[i])swap(a[i],a[re[i]]);
}
inline void Dft(comp *a,int len,int rev)
{
change(a,len);
for(register int h=2;h<=len;h<<=1)
{
comp step(cos(2.0*pi/h),rev*sin(2.0*pi/h));
for(register int j=0;j<len;j+=h)
{
comp w(1,0);
for(register int k=j;k<j+h/2;++k,w*=step)
{
comp u=a[k];
comp t=a[k+h/2]*w;
a[k]=u+t;
a[k+h/2]=u-t;
}
}
}
}快速傅里叶逆变换
前置芝士：逆元，NTT
逆元
即满足 $ax\equiv 1\mod p$ 其中 $a,p$ 互质，$x$ 即被称作 $a$ 关于 $p$ 的逆元
求解逆元: 一般用 $exged$ 或者 费马小定理
费马小定理求解逆元:
因为 $a^{p-1}\equiv 1\mod p$
所以 $a\cdot a^{p-2}\equiv 1 \mod p$
得出 $a$ 关于 $p$ 的逆元即为 $a^{p-2}$
快速数论变换(NTT)
关于NTT，我们很明显的看出它与FFT之间的关系(通过中文,它可以只在整数域内变换，完成$n\log n$多项式乘，具体实现我们使用原根 $g$ 代替了单位复数根 $\omega$ ，一般来说，NTT常用模数为998244353或者1004535809，且它们的原根都为3
这里的代替即我们让 $g^{(p-1)/n}$ 等价于 $e^{2\pi i/n}$并在运算的时候对模数取模运算即可
由于是整数运算，所以正常情况下要比复数运算的FFT快不少
非正常情况:有关字符串匹配的问题上，NTT要比FFT慢许多
