多项式入门

先贴个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慢许多