- 前言
- 三角函数
- 前前言
- 单位圆
- 公式
- 虚数
- 定义
- 公式
- 单位复根
- 坐标轴
- 定义
- 消去定理
- 消去定理的推论
- 折半定理
- 求和定理
- 多项式的表达
- 点值表达
- 系数表达
- 系数表达与点值表达的关系
- 快速傅里叶变换&快速傅里叶逆变换
- 快速傅里叶变换&快速傅里叶逆变换的优化
- 最终代码
这篇文章咕的很久，三角函数似乎没啥用。
三角函数似乎没啥用。三角函数似乎没啥用。三角函数似乎没啥用。
一个以原点为中心且半径为 (1)
[cos(alpha-beta)=cosalphacosbeta+sinalphasinbeta ]
[cos(alpha+beta)=cosalphacosbeta-sinalphasinbeta ]
[sin(alpha+beta)=sinalphacosbeta+cosalphasinbeta ]
[sin(alpha-beta)=sinalphacosbeta-cosalphasinbeta ]
作以 (x) 正半轴为始边，逆时针旋转 (alpha),(beta),(alpha-beta) 的终边与单位圆分别交于 (A(cos(alpha),sin(alpha))),(B(cos(beta),sin(beta))),(C(cos(alpha-beta),sin(alpha-beta))), (x) 正半轴与单位圆交于 (D(1,0)),有 (lvert AB vert = lvert CD vert)。
[(cosalpha-cosbeta)^2+(sinalpha-sinbeta)^2=(1-cos(alpha-beta))^2+sin^2(alpha-beta) ]
[begin{aligned} (cosalpha-cosbeta)^2+(sinalpha-sinbeta)^2&=cos^2alpha -2cosalphacosbeta+cos^2beta +sin^2alpha-2sinalphasinbeta+sin^2beta\ &=2-2cosalphacosbeta-2sinalphasinbeta\ (1-cos(alpha-beta))^2+sin^2(alpha-beta)&=1-2cos(alpha-beta)+cos^2(alpha-beta)+sin^2(alpha-beta)\ &=2-2cos(alpha-beta) end{aligned}]
[2-2cosalphacosbeta-2sinalphasinbeta=2-2cos(alpha-beta) ]
[cosalphacosbeta+sinalphasinbeta=cos(alpha-beta) ]
[cos(-beta)=cosbeta ]
[sin(-beta)=-sinbeta ]
[cos(alpha+beta)=cosalphacosbeta-sinalphasinbeta ]
[begin{aligned} sin(alpha+beta)&=cos(dfrac{pi}{2}-alpha-beta)=cos((dfrac{pi}{2}-alpha)-beta)\ &=cos(dfrac{pi}{2}-alpha)cosbeta+sin(dfrac{pi}{2}-alpha)sinbeta\ &=sinalphacosbeta+cosalphasinbeta end{aligned}]
[begin{aligned} sin(alpha-beta)&=sinalphacos(-beta)-cosalphasin(-beta)\ &=sinalphacosbeta-cosalphasinbeta end{aligned}]
[i=sqrt{-1} ]
[a+bi ]
[(a+bi)+(c+di)=(a+c)+(b+d)i ]
[(a+bi)-(c+di)=(a-c)+(b-d)i ]
[(a+bi) imes(c+di)=ac+adi+bci+bd imes(sqrt{-1})^2=(ac-bd)+(ad+bc)i ]
(x) 代表实数 (y)
(n) 次单位复根是满足 (omega_n^n=1) 的复数 (omega_n)，一共有 (n)
如何理解？画一个单位圆，将其 (n) 等分，圆上 (n) 个点就是 (n)
因此有：
[omega_n=cos(dfrac{2pi}{n})+sin(dfrac{2pi}{n})i ]
[omega_n^k=cos(dfrac{2pi}{n}k)+sin(dfrac{2pi}{n}k)i ]
[omega_{nm}^{km}=omega_n^k ]
[omega_{nm}^{km}=cos(dfrac{2pi}{nm}km)+sin(dfrac{2pi}{nm}km)i=cos(dfrac{2pi}{n}k)+sin(dfrac{2pi}{n}k)i=omega_n^k ]
[omega_n^{n/2}=omega_2=-1 ]
若 'n&1=0' 且 (n>0)，有：
[(omega_n^{k+n/2})^2=(omega_n^{k})^2 ]
[(omega_n^{k+n/2})^2=(omega_n^{k}omega_n^{n/2})^2=(omega_n{^k} imes(-1))^2=(omega_n^{k})^2 ]
对于任意整数 (1le n) 和不能被 (n) 整除的非负整数 (k)，有
[sum_{j=0}^{n-1}(omega_{n}^k)^j=0 ]
一个次数界为 (n) 的多项式 (A(x)) 的点值表达是一个由 (n)
[left{(x_0,y_0),(x_1,y_1),cdots,(x_{n-2}, y_{n-2}),(x_{n-1},y_{n-1}) ight} ]
其中 (x_i)
一个傻逼的性质， (A(x) = B(x) + C(x))
[A(x) = left{(x_0,By_0+Cy_0),(x_1,By_1+Cy_1),cdots,(x_{n-2},B y_{n-2}+C y_{n-2}),(x_{n-1},By_{n-1}+Cy_{n-1}) ight} ]
(A(x) = B(x) imes C(x))
[A(x) = left{(x_0,By_0 imes Cy_0),(x_1,By_1 imes Cy_1),cdots,(x_{n-2},By_{n-2} imes C y_{n-2}),(x_{n-1},By_{n-1} imes Cy_{n-1}) ight} ]
一个次数界为 (n) 的多项式 (A(x)) 的系数表达是一个由 (n)
[a_0x^0 + a_1x^1 + a_2x^2 + cdots + a_{n-2}x^{n-2}+a_{n-1}x^{n-1} ]
对于任意一个由 (n) 个点对组成的点值表达都有唯一一个次数界为 (n)
有 (y_i = A(x_i))。
把其写成矩阵形式：
( begin{bmatrix} 1 quad x_0 quad x_0^2 quad &cdots quad x_0^{n-1}\1 quad x_1 quad x_1^2 quad &cdots quad x_1^{n-1}\vdotsquadvdotsquadvdotsquad&ddotsquadvdots\1 quad x_{n-1} quad x_{n-1}^2 quad &cdots quad x_{n-1}^{n-1}\end{bmatrix}) (begin{bmatrix}a_0\a_1\vdots\a_{n-1}end{bmatrix}) (=) (begin{bmatrix}y_0\y_1\vdots\y_{n-1}end{bmatrix})
范德蒙德矩阵在 (x_i) 皆不同的情况下有逆矩阵，因此有点值表达，能够确定系数 (a_i)。
规定 (n) 是 (2) 的 (q)
已知
[A(x)=a_0x^0 + a_1x^1 + a_2x^2 + cdots + a_{n-2}x^{n-2}+a_{n-1}x^{n-1} ]
求
[left{(omega_n,y_0),(omega_n^1,y_1),cdots,(omega_n^{n-2}, y_{n-2}),(omega_n^{n-1},y_{n-1}) ight} ]
分治！！！
[A_0(x)=a_0x^0 + a_2x^1 + cdots + a_{n-2}x^{n/2-1} ]
[A_1(x)=a_1x^0 + a_3x^1 + cdots +a_{n-1}x^{n/2-1} ]
[A_2(x)=x ]
[A(x)=A_0(x^2)+A_2(x)A_1(x^2) ]
[A_0=left{(omega_{n/2},y_0),(omega_{n/2}^1,y_1),cdots,(omega_{n/2}^{n/2-2}, y_{n/2-2}),(omega_{n/2}^{n/2-1},y_{n/2-1}) ight} ]
[A_1=left{(omega_{n/2},y_0),(omega_{n/2}^1,y_1),cdots,(omega_{n/2}^{n/2-2}, y_{n/2-2}),(omega_{n/2}^{n/2-1},y_{n/2-1}) ight} ]
[A_2=left{(omega_{n},y_0),(omega_{n}^1,y_1),cdots,(omega_{n}^{n-2}, y_{n-2}),(omega_{n}^{n-1},y_{n-1}) ight} ]
[A(omega_{n}^{i})=A_0(omega_{n}^{2i})+omega_{n}^{i}A_1(omega_{n}^{2i}) ]
[A(omega_{n}^{i})=A_0(omega_{n/2}^{i})+omega_{n}^{i}A_1(omega_{n/2}^{i}) ]
注意，(omega_{n/2}^{i}) 在 (A_0) 和 (A_1)
巨丑的伪代码：
这样写为什么是对的？？？
[begin{aligned} y0_k&=A0(omega_{n/2}^{k})\ y1_k&=A1(omega_{n/2}^{k})\ y_k&=A(omega_{n}^{k})\ A(omega_{n}^{k})&=y0_k+omega_{n}^{k}y1_k\ &=A0(omega_{n/2}^{k})+omega_{n}^{k}A1(omega_{n/2}^{k})\ A(omega_{n}^{k+n/2})&=A0((omega_{n}^{k+n/2})^2)+omega_{n}^{k+n/2}A1((omega_{n}^{k+n/2})^2)\ &=A0(omega_{n}^{2k})+omega_{n}^{n/2}omega_{n}^{k}A1(omega_{n}^{2k})\ &=A0(omega_{n/2}^{k})+(-1)omega_{n}^{k}A1(omega_{n/2}^{k})\ &=A0(omega_{n/2}^{k})-omega_{n}^{k}A1(omega_{n/2}^{k})\ end{aligned} ]
已知
[left{(omega_n,y_0),(omega_n^1,y_1),cdots,(omega_n^{n-2}, y_{n-2}),(omega_n^{n-1},y_{n-1}) ight} ]
求
[A(x)=a_0x^0 + a_1x^1 + a_2x^2 + cdots + a_{n-2}x^{n-2}+a_{n-1}x^{n-1} ]
有
[ begin{bmatrix} 1 &1 &1 &1 &1 &cdots &1\ 1 &omega_{n}^{1} &omega_{n}^{2} &omega_{n}^{3} &omega_{n}^{4} &cdots &omega_{n}^{n-1}\ 1 &omega_{n}^{2} &omega_{n}^{4} &omega_{n}^{6} &omega_{n}^{8} &cdots &omega_{n}^{2(n-1)}\ 1 &omega_{n}^{3} &omega_{n}^{6} &omega_{n}^{9} &omega_{n}^{12} &cdots &omega_{n}^{3(n-1)}\ 1 &vdots &vdots &vdots &vdots &ddots &vdots\ 1 &omega_{n}^{n-1}&omega_{n}^{2(n-1)}&omega_{n}^{3(n-1)}&omega_{n}^{4(n-1)}&cdots &omega_{n}^{(n-1)(n-1)} end{bmatrix} begin{bmatrix} a_0\ a_1\ a_2\ a_3\ vdots\ a_{n-1} end{bmatrix} = begin{bmatrix} y_0\ y_1\ y_2\ y_3\ vdots\ y_{n-1} end{bmatrix} ]
[V_n= begin{bmatrix} 1 &1 &1 &1 &1 &cdots &1\ 1 &omega_{n}^{1} &omega_{n}^{2} &omega_{n}^{3} &omega_{n}^{4} &cdots &omega_{n}^{n-1}\ 1 &omega_{n}^{2} &omega_{n}^{4} &omega_{n}^{6} &omega_{n}^{8} &cdots &omega_{n}^{2(n-1)}\ 1 &omega_{n}^{3} &omega_{n}^{6} &omega_{n}^{9} &omega_{n}^{12} &cdots &omega_{n}^{3(n-1)}\ 1 &vdots &vdots &vdots &vdots &ddots &vdots\ 1 &omega_{n}^{n-1}&omega_{n}^{2(n-1)}&omega_{n}^{3(n-1)}&omega_{n}^{4(n-1)}&cdots &omega_{n}^{(n-1)(n-1)} end{bmatrix}]
[V_n^{-1}= dfrac{1}{n} begin{bmatrix} 1 &1 &1 &1 &1 &cdots &1\ 1 &omega_{n}^{-1} &omega_{n}^{-2} &omega_{n}^{-3} &omega_{n}^{-4} &cdots &omega_{n}^{-(n-1)}\ 1 &omega_{n}^{-2} &omega_{n}^{-4} &omega_{n}^{-6} &omega_{n}^{-8} &cdots &omega_{n}^{-2(n-1)}\ 1 &omega_{n}^{-3} &omega_{n}^{-6} &omega_{n}^{-9} &omega_{n}^{-12} &cdots &omega_{n}^{-3(n-1)}\ 1 &vdots &vdots &vdots &vdots &ddots &vdots\ 1 &omega_{n}^{-(n-1)}&omega_{n}^{-2(n-1)}&omega_{n}^{-3(n-1)}&omega_{n}^{-4(n-1)}&cdots &omega_{n}^{-(n-1)(n-1)} end{bmatrix}]
[V_n^{-1}V_n=begin{bmatrix} 1 &0 &0 &cdots &0\ 0 &1 &0 &cdots &0\ 0 &0 &1 &cdots &0\ 0 &vdots &vdots &ddots &vdots\ 0 &0 &0 &cdots &1 end{bmatrix}]
[[V_n^{-1}V_n]_{i,j}=sum_{k=0}^{n-1} (omega_n^{-ki}/n)(omega_n^{kj}) =sum_{k=0}^{n-1}omega_n^{kj-ki}/n ]
应用求和引理。
在看原来的柿子：
[left{(omega_n,y_0),(omega_n^1,y_1),cdots,(omega_n^{n-2}, y_{n-2}),(omega_n^{n-1},y_{n-1}) ight} ]
求
[A(x)=a_0x^0 + a_1x^1 + a_2x^2 + cdots + a_{n-2}x^{n-2}+a_{n-1}x^{n-1} ]
有
[a_j=dfrac{1}{n}sum_{k=0}^{n-1}y_komega_{n}^{-kj} ]
稍微变换一下 (FFT)
改成迭代计算即可，因为在同一层的计算会用到相同的单位复根，可以减少常数。
简单的说，将序列位逆序置换，得到最低层的计算顺序，然后不断向上计算，调整位置（实际上在合并时就自动调整位置了）。