多项式学习笔记

本文为作者的学习笔记，其中主要包含作者学习时的一些笔记，以及一些例题。如果有小伙伴看到这篇博客没有写完的话，那一定是我咕咕咕了。

FFT

FFT 的中文名称为快速傅里叶变换，英文全称为 Fast Fourier Transform。

系数表示法

我们知道，每一个多项式都有唯一的一组系数，每一组系数也对应着唯一的一个多项式，所以我们可以用一组系数来表示一个多项式：

点值表示法

我们可以把这个多项式看作平面直角坐标系上的一个函数，那么我们就可以从上面选 $ n+1 $ 个点，这些点也可以唯一表示这个多项式。

为什么这么说呢？我们假设这 $ n+1 $ 个点分别是 $ (x_0,y_0),(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n) $。

那么我们可以由此列出方程：

我们将这些 $ x_i $ 和 $ y_i $ 带入方程组中，便得到了一个有 $ n+1 $ 个方程和 $ n+1 $ 个未知数的方程组，我们正好可以解得唯一的一组 $ a $，也就可以表达这个多项式了。

FFT的基本理论

假如说我们要求出两个多项式 $ f(x),g(x) $ 的乘积 $ h(x) $，那么 FFT 是如何求出 $ h(x) $ 的值的呢？

首先，我们还是把 $ f(x) $ 与 $ g(x) $ 由系数表示法变为点值表示法，这个过程被叫为 DFT。

假设函数 $ f(x) $ 对应的点坐标分别为 $ (x_i,y_{0,i}) $，函数 $ g(x) $ 对应的点坐标分别为 $ (x_i,y_{1,i}) $。（没错，他们的横坐标要相等）

那么我们就可以得到 $ h(x)={(x_0,y_{0,0}y_{1,0}),(x_1,y_{0,1}y_{1,1}),(x_2,y_{0,2}y_{1,2}),\cdots,(x_n,y_{0,n}y_{1,n})} $。

为什么将这两个函数的纵坐标相乘就得到了 $ h(x) $ 的纵坐标呢？下面我们来证明。

假设 $ f(x),g(x),h(x) $ 的系数分别为 $ a_{0,i},a_{1,i},a_{2,i} $ , $ h(x) $ 对应点的纵坐标为 $ y_{2,i} $ 。

因为 $ h(x)=f(x)g(x) $，那么就会有 $ a_{0,i}a_{1,j}=a_{2,i+j} $。

$ \therefore $ 将 $ f(x) $ 与 $ g(x) $ 的纵坐标相乘便得到了 $ h(x) $ 的横坐标。

那么现在我们知道了 $ h(x) $ 的点值表示法，现在我们就可以将他表示为系数表示法，这个过程被叫为 IDFT。

FFT 的理论就是这个样子，但是我们也知道 DFT 暴力的时间复杂度为 $ O(n^2) $，IDFT 采用高斯消元的做法时间复杂度也为 $ O(n^3) $。显然，FFT 的效率还不如暴力高。那么我们的主要问题就为优化 FFT 了。

当然，上述做法有一些漏洞。假如 $ f(x) $ 与 $ g(x) $ 的最高次项系数都为 $ n $，那么 $ h(x) $ 的最高次项系数就是 $ 2n $。此时肯定是无法用 $ n+1 $ 个点表达 $ h(x) $ 这个多项式了。

坐标的取值

我们会发现无论如何，似乎 FFT 的时间复杂度都无法得到有效的优化，那么如果我们取的横坐标是一些特殊的值呢？

复数

设方程 $ x^n=1 $ 在复数意义下的解是 $ n $ 次复根，那么这样的解显然会有 $ n $ 个。设 $ \omega_n=e^\frac{2\pi i}{n} $，那么 $ x^n=1 $ 这个方程的解为 $ \omega_n^k{k|0,1,\cdots,n-1} $。

另一方面我们可以根据欧拉公式，也可以得到 $ \omega_n=e^\frac{2\pi i}{n}=\cos\left(\dfrac{2\pi}{n}\right)+i\times \sin\left(\dfrac{2\pi}{n}\right) $。

放一张 oi-wiki 上的图片，有助于理解。

复数的性质

对于任意的正整数 $ n $ 及整数 $ k $。

复数的运算

设 $ x=ai+b,y=ci+d $，下面我们来推导复数的计算。

复数的除法也是可以推导的，不过我们暂时用不到。

我们可以打出一份复数的结构体。

struct fs//因为英语不好，所以就用拼音了......
{
	double x,y;//x为实部，y为虚部，也就是说这个复数为x+yi
	fs(double xx=0,double yy=0){ x=xx,y=yy;}
	fs operator + (fs b){ return fs(x+b.x,y+b.y);}
	fs operator - (fs b){ return fs(x-b.x,y-b.y);}
	fs operator * (fs b){ return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
};

DFT

首先我们要将一个函数由系数表示法变为点值表示法，我们设这个函数为 $ f(x) $，且第 $ i $ 项的系数为 $ a_i $。

为了方便起见，我们设 $ f(x) $ 的项数 $ n $ 为 $ 2 $ 的整数次幂，如果项数不够可以补齐。

首先我们设：

//这里前面还需要复数的结构体，但是前面已经打过了，不再重复
const double PI=acos(-1);//这个函数可以得到精确的圆周率
fs omega(int n){ return fs(cos(2*PI/n),sin(2*PI/n));}
void DFT(fs *a,int n)
{
    if(n==1) return ;
	vectormem(n);//开一个数组记录之前的值
	for(int i=0;i

//这里前面还需要复数的结构体，但是前面已经打过了，不再重复
const double PI=acos(-1);//这个函数可以得到精确的圆周率
fs omega(int n){ return fs(cos(2*PI/n),sin(2*PI/n));}
void IDFT(fs *a,int n)
{
    if(n==1) return ;
	vectormem(n);//开一个数组记录之前的值
	for(int i=0;i

#include
#include
#include
using namespace std;
const double PI=acos(-1);//这个函数可以得到精确的圆周率
struct fs//因为英语不好，所以就用拼音了......
{
	double x,y;//x为实部，y为虚部，也就是说这个复数为x+yi
	fs(double xx=0,double yy=0){ x=xx,y=yy;}
	fs operator + (fs b){ return fs(x+b.x,y+b.y);}
	fs operator - (fs b){ return fs(x-b.x,y-b.y);}
	fs operator * (fs b){ return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
};
fs omega(int n){ return fs(cos(2*PI/n),sin(2*PI/n));}
fs a[5000000];
fs b[5000000];
void DFT(fs *a,int n,bool dft)
{
    //当dft为1的时候，进行DFT
    //当dft为0的时候，进行IDFT
    if(n==1) return ;
	vectormem(n);//开一个数组记录之前的值
	for(int i=0;i

//wh[i]表示i这个数经过翻转以后所对应的值
//wh[0]=0,不进行计算
for(int i=1;i>1]>>1)+((i&1)?n>>1:0);
//当i的最后一位为0时，wh[i]=(wh[i>>1]>>1)
//当i的最后一位为1时，wh[i]=(wh[i>>1]>>1)+(n>>1)
//这个显然是正确的，道理和上面证明的过程差不多。

#include
#include
#include
using namespace std;
const double PI=acos(-1);
struct fs
{
	double x,y;
	fs(double xx=0,double yy=0){ x=xx,y=yy;}
	fs operator + (fs b){ return fs(x+b.x,y+b.y);}
	fs operator - (fs b){ return fs(x-b.x,y-b.y);}
	fs operator * (fs b){ return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
};
fs omega(int n){ return fs(cos(2*PI/n),sin(2*PI/n));}
fs step[5000001];
int wh[5000001];
fs a[5000000];
fs b[5000000];
int n,m;
void DFT(fs *a,int n,bool dft)
{
	for(int i=0;iwh[i])...
	for(int len=2;len<=n;len<<=1)
	{
		fs ste=step[len];
		if(!dft) ste.y=-ste.y;
		for(int l=0;l>1]>>1)+((i&1)?n>>1:0);
	DFT(a,n,1),DFT(b,n,1);
	for(int i=0;i

#include
#include
#include
using namespace std;
const double PI=acos(-1);
struct fs
{
    double x,y;
    fs(double xx=0,double yy=0){ x=xx,y=yy;}
    fs operator + (fs b){ return fs(x+b.x,y+b.y);}
    fs operator - (fs b){ return fs(x-b.x,y-b.y);}
    fs operator * (fs b){ return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
};
fs omega(int n){ return fs(cos(2*PI/n),sin(2*PI/n));}
fs step[5000001];
int wh[5000001];
fs a[5000000];
int n,m;
void DFT(fs *a,int n,bool dft)
{
    for(int i=0;iwh[i])...
    for(int len=2;len<=n;len<<=1)
    {
        fs ste=step[len];
        if(!dft) ste.y=-ste.y;
        for(int l=0;l>1]>>1)+((i&1)?n>>1:0);
    DFT(a,n,1);
    for(int i=0;i