多项式与多项式乘法

摘要

鸽鸽给我们讲课啦

据说讲课前通宵玩了两天。早上灵车漂移。

多项式

定义

给定一个环 ,( 通常是交换环,可以是有理数、实数或者复数等等)以及一个未知数 x,则任何形同

的代数表达式是 上的一元多项式。其中 中的元素。未知数不代表任何值,但环 上的所有运算都对它适用。在不至于混淆的情形下,一般将一元多项式简称为多项式。

多项式的表示

系数表示法:即使用 个系数表示 次多项式

点值表示法:对于 次多项式,给出它在 个地方的取值,就可以唯一确定一个多项式。即用 个点表示多项式 。点值可以自己指定。

多项式加减法

两种表示法都可以快速计算

多项式乘法

系数表示法,需要拆开一个一个相乘,复杂度是

其中 序列表示 的系数序列

而点值表示法只需要将对应点的函数值相乘即可,复杂度 .

因此多项式乘法(卷积)的快速计算就可以借助点值表示法快速完成。

复数

复数(Complex)是数论研究领域的一个重要分支。学习多项式或多或少会牵涉这方面的知识,在此做一些必要性的介绍。

定义

复数可以写为 的形式;其中 。称 为实部, 为虚部。 是一个虚数单位,满足

复数的集合记作 .

复平面

数学中,复平面(Complex Plane)是用水平的实轴与垂直的虚轴建立起来的复数的几何表示。它可视为一个具有特定代数结构笛卡儿平面(实平面),一个复数的实部用沿着 轴的位移表示,虚部用沿着 轴的位移表示。

一个虚数 可以用复平面上的点 表示,也可以理解为一个向量。

复数的运算

对于加减乘除的运算可以当作多项式的运算。对于 ,有

加法减法对应的几何意义就是复平面上向量的加减,而乘法除法运算对应复平面上的旋转积长,放一张图

pic

有这样一个比较重要的性质:

的角度。通俗的解释, 的向量相当于 向量角度相加,长度相乘的结果。

证明?算 tan 即可。

有了这样的几何意义,我们就能方便地理解单位根的定义。这里给一个复数的模板

struct complex{
    double a,b;//a+bi
    complex(double _a=0,double _b=0){a=_a,b=_b;}//initialize
    complex operator+(complex c){return complex(a+c.a,b+c.b);}
    complex operator-(complex c){return complex(a-c.a,b-c.b);}
    complex operator*(complex c){return complex(a*c.a-b*c.b,a*c.b+b*c.a);}
};

单位根

数学上, 次单位根是 次幂为 1 的复数,记为 。它们位于复平面的单位圆上,构成正 边形的顶点,其中一个顶点是 1。为什么它们在单位圆上呢?因为它们的长度相乘恒为 1,所以相当于长度为 1 的向量旋转。

单位根的向量与 轴非负半轴的夹角是一个单位角,它的整数幂的向量把这个圆等分成 份,因此单位角的大小为 .

那么根据三角函数在单位圆中的定义,我们可以求出单位根对应的复数为

坐标表示为

单位根的性质

单位根有两个重要性质:

第一个性质相当于把每个单位角又分成两半;

第二个性质相当于转了半圈,转到对称点(相反数)的位置了(要求 的倍数)。

这个单位根是干嘛的呢?当然是用来帮助多项式乘法的快速计算啦。

傅里叶变换

回顾多项式的两种表示法。把多项式的系数序列转化为点值序列称为 DFT(Fast Fourier Transform,傅里叶变换),反之称为 IDFT(Inverse Fast Fourier Transform,傅里叶逆变换)。

直接做 DFT 的复杂度是 的,而快速傅里叶变换(Fast Fourier Transform)可以更加高效地完成变换。

FFT 干的事情就是把 次多项式 的系数序列 变换为点值序列 . 当然我们不会保存 的值,所以实际上转换成的序列是

分治法

那么怎么做呢?考虑分治

我们针对 的系数序列奇偶分组,构造

接下来考虑 的取值。我们取 ,令 为偶数。

这里用到了单位根的两个性质。

那么要同时求 ,就只需要处理出 的值就可以了

由于在分治的过程中要求每次 都整除 2,因此原多项式的项数必须是 的整数次幂,那么高位系数要预先用 0 填充。

其次,在 的时候, ,这里 是某一个系数,取决于递归到哪一个位置

然后在返回的时候归并一下即可。

蝴蝶变换

蝴蝶变换指的是将原系数序列按奇偶前后分组若干次后的系数序列。例如 的蝴蝶变换过程是这样的

最后每个元素单独成一个子序列。这样的变换有什么特点吗?当然有

变换前后序列的下标在二进制下是一一翻转的:

原下标 二进制 二进制翻转 现下标
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 001 3
7 111 111 7

而从原下标到现下标的变换就是蝴蝶变换!

那么这东西有什么用?它可以帮我们实现非递归版本的 FFT。

注意到蝴蝶变换其实含有这样的意义

当序列长度为 1 的时候, ,那么单位根只能取 ,所以蝴蝶变换完后的序列刚好表示

那么因为

同时 ,那么我们计算的 会分别记录在 的位置。其他的同理。也就是说,一次合并(步长为 1)后序列表示

同理,这次则是隔一个合并一个(步长为 2),合并 ,分别存在对应的位置。这次合并后的序列表示

最后合并(步长为 4), 变成 .

变换结束。每次合并会操作整个序列,步长是倍增的,复杂度

傅里叶逆变换

傅里叶逆变换就是把点值表示法还原为系数表示法。朴素算法可以使用拉格朗日插值法做到 的复杂度。当然我们也有快速傅里叶逆变换(Inverse Fast Fourier Transform)来完成这个过程。

这东西怎么做呢?我们考虑构造法。我们已知 ,那么构造多项式

相当于把 当做 的系数序列。那么给定点 ,则 的点值序列为

考虑 的值

时,

时,我们错位相减一下,得到

也就是说

那么代回原式

也就是说给定点 ,则 的点值序列为

那么事情就很好办啦,我们把取单位根为其倒数,对 跑一遍 FFT,然后除以 即可得到系数序列啦

这里贴一道洛谷的模板题。因为涉及到蝴蝶变换的求法,所以给出完整代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<assert.h>
#define PI M_PI
using namespace std;
const int N=(1<<21)+5;
struct cpx{
    double a,b;
    cpx(double _a=0,double _b=0){a=_a,b=_b;}
    cpx operator+(cpx c){return cpx(a+c.a,b+c.b);}
    cpx operator-(cpx c){return cpx(a-c.a,b-c.b);}
    cpx operator*(cpx c){return cpx(a*c.a-b*c.b,a*c.b+b*c.a);}
};
int tr[N],dgl;// 蝴蝶变换的下标
void trans(cpx *y,int len){for(int i=1;i<len;i++)if(i<tr[i])swap(y[i],y[tr[i]]);}
void fft(cpx *y,int len,int tag){
    trans(y,len);// 蝴蝶变换
    for(int j=1;j<len;j<<=1){
        cpx wn(cos(PI/j),sin(tag*PI/j));//w_(2*j) 的单位根,2*PI/(2*j)=PI/j
        for(int i=0;i<len;i+=j<<1){
            cpx w(1,0),u,v;//0 次方
            for(int k=i;k<i+j;k++)
                u=y[k],v=y[k+j]*w,y[k]=u+v,y[k+j]=u-v,w=w*wn;
        }
    }
    if(tag==-1)for(int i=0;i<len;i++)y[i].a/=len;// 实部
}
int n,m,len=1;
cpx f[N],g[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0,a;i<=n;i++)scanf("%d",&a),f[i]=cpx(a,0);
    for(int i=0,a;i<=m;i++)scanf("%d",&a),g[i]=cpx(a,0);
    while(len<m+n+2)len<<=1,dgl++;
    for(int i=1;i<len;i++)tr[i]=(tr[i>>1]>>1) | (i&1)<<(dgl-1);// 蝴蝶变换预处理
    fft(f,len,1),fft(g,len,1);
    for(int i=0;i<len;i++)f[i]=f[i]*g[i];
    fft(f,len,-1);
    for(int i=0;i<=m+n;i++)printf("%d",(int)(f[i].a+0.2));
    return 0;
}

数论变换

学习数论变换(Number-Theoretic Transform)首先要理解原根相关的知识,可以移步原根与模算术。由于在复数意义下的多项式计算存在精度的问题,数论变换更适合模意义下多项式的系数表示法到点值表示法的变换。

在 FFT 的过程中主要依靠单位根的两个重要性质:周期性与对称性。那么在模意义下有没有这样的数呢?有啊。就是原根。数论变换要求在模质数 P 意义下,设 P 的原根是 g,则有

因此在 原根的幂互不相同,则二次剩余是唯一的。换言之,对于 在模 意义下是唯一存在的。同时根据上式可以得到 ,因此周期为 。在 FFT 中我们将单位圆分割成 2 的整数次幂个部分。因此我们希望 也被 2 的整数次幂整除。最常见的 P 是 。这样就可以在 的范围内做 NTT 啦。

更形式化地说,我们设 表示模 意义下的原根。 我们可以理解为“模意义下的 n 次单位根”(显然当 就是原根)于是有两条美妙的性质:

于是就可以快速变换啦

多项式求逆

对于一个多项式 ,如果存在 满足

那么称 意义下的逆元(inverse element),记作 . 其中 。如果模数不是 2 的整数次幂,那么就把它补成整数次幂。

这个怎么求呢?我们考虑倍增法。我们已知 使得

假设我们已经知道了 使得

我们尝试建立 的递推式。首先根据同余的性质,把两个方程相减放在 意义下有

由于 ,于是可以直接消掉:

把等式两边同时平方(这时模数也平方)并化简得到

于是我们可以构造一下,把 乘回去并把括号打开:

(注意在 意义下

那么 FFT 或者 NTT 即可

参考文献

Wikipedia. 多项式 . https://zh.wikipedia.org/zh-cn/%E5%A4%9A%E9%A0%85%E5%BC%8F

Wikipedia. 复平面 . https://zh.wikipedia.org/wiki/%E5%A4%8D%E5%B9%B3%E9%9D%A2

OI-Wiki. 快速傅里叶变换 . https://oi-wiki.org//math/fft/


 上一篇
[BZOJ5372] 神仙的游戏 [BZOJ5372] 神仙的游戏
摘要 一道综合生成函数和多项式乘法的题 这道题提醒我,空间一定要开够!(记得双倍,尤其是计算长度的时候) 题意定义字符串 的 border 是满足以下条件的 : \forall i\in\{1,2
2019.02.15
下一篇 
筛法自闭 筛法自闭
摘要 tqy 奆奆继续给我们讲数论啦 洲阁筛待更 数论函数与积性函数数论函数,积性函数,完全积性函数的定义、性质 常见数论函数 SPOJ DIVCNT1 \sum_{i=1}^n\sigma(i)\\ =\sum_{i=1}^n\sum_
2019.02.14
  目录