复数
复数的表示
形如a+bi)的实数成为复数
a称为实部，b称为虚部，i为虚数单位i=sqrt{-1}))
以R)实部)为x)轴，以i)虚部)为y)轴
可以将一个复数表示为该二维平面内的一个向量
复数的模长和辅角
复数的模长即对应向量的模长r=sqrt{a^2+b^2})
辅角arg)为该向量与x)轴正半轴的夹角
辅角有无限多个，每个相差2kpi,kin Z))
那么a=rcos arg~,b=rsin arg)
则a+bi=rcos arg+isin arg))
复数的加法
a+bi)+c+di)=a+c)+b+d)i)
可以看做是该二维平面中向量的加法
满足三角形法则和平行四边形法则
复数的乘法
记x=a+bi=rcos p+isin p))，y=c+di=tcos q+isin q))
[egin{aligned}
xy&=rtcos pcos q-sin psin q+icos psin q+sin pcos q))\
&=rtcosp+q)+isinp+q))
end{aligned}
]
因此有
|xy|=|x||y|)
argxy)=argx)+argy))
复数的n次根
x=a+bi=rcos p+isin p))
x^{frac 1 n})表示满足y^n=x的所有y)
根据乘法的性质可知
y=r^{frac 1 n}leftcosfrac{p+2kpi}{n}+isinfrac {p+2kpi}{n}ight))
可知当k=0dots n-1)时，y)表示不同的n)个复数
即一个数的n)次单位根有n)个
几何意义上，它们组成圆内接的一个正n)边形
n次单位根
定义r=1,arg=0)时即复数等于实数1)时
复数的n次根为n次单位根
n次单位根x)满足
x=rleftcosfrac{2kpi}{n}+isinfrac{2kpi}{n}ight))
可知n)次单位根在复数平面的单位圆上，把圆n)等分
且n)个n)次单位根组成n)次单位根群乘群)
将群中的生成元记作本原单位根
取其中一个记为omega_n)
一般选omega_n=cos frac {2pi}{n}+isinfrac{2pi}{n})
根据欧拉公式 e^{ix}=cos x+isin x)
则$$omega_n=e^frac {2pi~i}{n}$$
可以用omega_n^k,k=0dots n-1)来表示其它的n)个单位根
n次单位根的性质
omega_n^k=e^{frac {2kpi i} n}=cosfrac{2kpi}{n}+isinfrac{2kpi}{n})
omega_n^k=omega_{n/2}^{k/2})
omega_n^k=omega_n^{k~mod~n})
omega_n^{n/2+k}=omega_n^{n/2}omega_n^k=e^{ipi}omega_n^k=-omega_n^k)（几何理解：转半个圆）
frac 1 nsum_{i=0}^{n-1} omega_n^{ki}=[k~mod~n=0])
（当k~mod~n=0)时全为1，否则为等比数列,和为frac {omega_n^{nk}-1}{omega_n^k-1}=0)）
形式幂级数
[Fx)=sum_{i=0}^n f_ix^i
]
基本记号
F+G)x)=sum_{i=0}^nf_i+g_i)x^i)
F imes G)x)=sum_{i=0}^{2n}leftsum_{j+k=i}f_jg_kight)x^i)
Fcdot G)或FG)表示点乘（对应位相乘）
F^nx)=prod_{i=1}^n Fx))
deg F)表示F)的最高次数
没有声明的情况下，大写字母表示多项式，对应小写字母表示该多项式的系数
定义乘法
即多项式乘法
就是上面的F imes G)啦
运算律
乘法满足结合率，交换律，对加法的分配率
复数域卷积
DFT的推导
利用一个if语句frac 1 nsum_{i=0}^{n-1} omega_n^{ki}=[k~mod~n=0])
设C=A imes B)
则
[egin{aligned}
c_k&=sum_{i+j=k} a_ib_j\
&=sum_isum_j[i+j=k]a_ib_j\
&令n为一个比deg A+deg B)大的数\
&=sum_isum_j[i+jequiv kmod~n)] a_ib_j\
&=sum_isum_j[i+j-k)~mod~n=0]a_ib_j\
&=sum_isum_jfrac 1 nsum_{l=0}^{n-1}omega_n^{i+j-k)l} a_ib_j\
&=frac 1 nsum_{l=0}^{n-1}omega_n^{-kl}leftsum_iomega_n^{il}a_iight)leftsum_jomega_n^{jl}b_jight)\
&=frac 1 nsum_{l=0}^{n-1}omega_n^{-kl} Aomega_n^l)Bomega_n^l)\
end{aligned}
]
DFT可以看做求点值
IDFT可以看做插值我们之前令n)为比deg A+deg B=deg C)大的数)
DFT的性质
DFT[i]A)=sum_{j=0}^{n-1} a_jomega_n^{ij}=Aw_n^i))
IDFT[i]A)=frac 1 nsum_{j=0}^{n-1}a_jomega_n^{-ij})
1.DFTk_1A+k_2B)=k_1DFTA)+k_2DFTA))
2.DFTA imes B)=DFTA)cdot DFTB))
3.A=IDFTDFTA)))
FFT优化
[egin{aligned}
&当kle n/2时\
Aomega_n^k)&=A_0omega_n^{2k})+omega_n^kA_1omega_n^{2k})\
&=A_0omega_{n/2}^k)+omega_n^kA_1omega_{n/2}^k)\\
&当kgt n/2时\
Aomega_n^k)&=A_0omega_n^{2k})+omega_n^kA_1omega_n^{2k})\
&=A_0omega_{n/2}^k)+omega_n^kA_1omega_{n/2}^k)\
&=A_0omega_{n/2}^{k-n/2})-omega_n^{k-n/2}A_1omega_{n/2}^{k-n/2})\\
&则对于j=i+n/2时\
A_i&=A_0i+omega_n^i A_1i\
A_j&=A_0i-omega_n^i A_1i\
end{aligned}
]
取n为满足之前条件的最小的2的整数次幂即可)
这样我们可以对奇数位算DFT，对偶数位算DFT，这样递归计算
最后的式子称蝶形运算
总复杂度是Tn)=2Tn/2)+On))的
根据主定理Tn)=Onlog n))
逆运算的式子长得差不多，处理也是同理的
具体实现网上很多本文不细说
mod P域卷积
模数为质数
所以该环是一个域（有单位元1，且除非零元外有逆元）
1)的P-1)次单位根是满足之前单位根的性质的（满足下标是整数的条件下）
设P-1=2^m*C)
当2^m)比deg C)大时
我们就可以用原根来替代omega)
判断原根与寻找原根
bool okLL x,int p)
{//类似某题分解质因数判原根的方法，单次log
int l=p-1,i,L=p-1;//根据欧拉，p以内的最长循环节为p-1
fori=2;i*i<=l;i++) ifl%i==0){
ifpwdx,L/i,p)==1) return 0;
whilel%i==0) l/=i;
}
ifl>1&&pwdx,L/l,p)==1) return 0;
return 1;
}
LL getrtint p)
{
ifp==2) return 1;
int res=2;
for;!okres,p);res++);
return res;
}
NTT
数论变换
不同于omega_n=]cos2pi/n)+isin2pi/n))可以直接计算
NTT实现的时候要预处理g_n)，不然每次快速幂算总复杂度Onlog^2n))
NTT的性质与FFT相同，具体实现上网找
其它域上的卷积
待补多项式导论
集合幂级数
[Fx)=sum_{sin 2^U}f_sx^s
]
基本记号
U={1cdots n}),代表本文的全集
记2^X)表示集合X)的幂集，即所有X)的子集组成的集合
记s_x)表示集合s的二进制第x位
|s|)表示bitcountx)
在Fx)=sum_{sin 2^U}f_sx^s)式子中
f_s表示第s项系数，f_sx^s没有乘法的意思，x^s代表是第s项)
e.g.~~Fx)=5x^{phi}+9x^{{1}}+3x^{{1,2}})
表示f_{phi}=5,f_{{1}}=9,f_{{1,2}}=3)
乘法定义
注意学会类比
我们希望乘法也满足结合律，交换率，对加法的分配率
常见的几种乘法：对称差oplus)，并cap)，或cup)
对于集合幂级数A,B)
Acup B)x)=sum_{kin 2^U}leftsum_{icup j=k}a_ib_jight)x^k)
Acap B)x)=sum_{kin 2^U}leftsum_{icap j=k}a_ib_jight)x^k)
Aoplus B)x)=sum_{kin 2^U}leftsum_{ioplus j=k}a_ib_jight)x^k)
FWT的推导
复数有一个if)语句性质，这边也找一个？
x-1)^n=sum_{i=0}^ninom n i-1)^i x^{n-i})
所以1-1)^n=sum_{i=0}^ninom n i-1)^i=[n=0])
推广一下得到
[egin{aligned}
&frac 1 {2^n}sum_{Tin 2^U}-1)^{|Scap T|}=[S=phi]1)\
&sum_{Tsubseteq Xsubseteq S}-1)^{|S|-|X|}=[T=S]2)\
&sum_{Tsupseteq Xsupseteq S}-1)^{|X|-|S|}=[T=S]3)\
end{aligned}
]
（注：除了下面推导的式子以外，不排除有其它形式的FWT式子，合理即可）
于是我们以oplus)为例推导
设C=Aoplus B),使用if语句1)
[egin{aligned}
C_k&=sum_{iin 2^U}sum_{jin 2^U}[ioplus joplus k=phi]a_ib_j\
&=sum_{iin2^U}sum_{jin 2^U}frac 1 {2^n}sum_{lin 2^U}-1)^{|ioplus joplus k)cap l|} a_ib_j\
&=sum_{iin2^U}sum_{jin 2^U}frac 1 {2^n}sum_{lin2^U}-1)^{sum_{x=0}^{n-1}~~i_x+j_x+k_x)*l_x}a_ib_j~~注:-1自带mod~2)\
&=frac 1 {2^n}sum_{lin2^U}-1)^{|kcap l|}leftsum_{iin2^U}-1)^{|icap l|}a_iight) leftsum_{jin 2^U}-1)^{|jcap l|}b_jight)
end{aligned}
]
另外两个运算的推导可以先自己尝试推一推
设C=Acup B),使用if语句2)
[egin{aligned}
C_k&=sum_{iin2^U}sum_{jin 2^U} [icup j=k]a_ib_j\
&=sum_{iin2^U}sum_{jin2^U}sum_{icup j)subseteq lsubseteq k}-1)^{|k|-|l|} a_ib_j\
&=sum_{iin2^U}sum_{jin2^U}sum_{lsubseteq k}-1)^{|k|-|l|}[icup j)subseteq l]a_ib_j\
&因为[icup jsubseteq l]Leftrightarrow [isubseteq l][jsubseteq l]\
&=sum_{lsubseteq k}-1)^{|k|-|l|}leftsum_{isubseteq l}a_iight)leftsum_{jsubseteq l} b_jight)\
end{aligned}
]
设C=Acap B),使用if语句3)
[egin{aligned}
C_k&=sum_{iin2^U}sum_{jin 2^U} [icap j=k]a_ib_j\
&=sum_{iin2^U}sum_{jin2^U}sum_{icup j)supseteq lsupseteq k}-1)^{|l|-|k|} a_ib_j\
&=sum_{iin2^U}sum_{jin2^U}sum_{lsupseteq k}-1)^{|l|-|k|}[icap j)supseteq l]a_ib_j\
&因为[icap jsupseteq l]Leftrightarrow [isupseteq l][jsupseteq l]\
&=sum_{lsupseteq k}-1)^{|l|-|k|}leftsum_{isupseteq l}a_iight)leftsum_{jsupseteq l} b_jight)\
end{aligned}
]
FWT的性质
不证了也不难证
FWTk_1A+k_2B)=k_1FWTA)+k_2FWTB))
FWTAoplus B)=FWTA)cdot FWTB))
A=IFWTFWTA)))
FWT的优化
注意到DFT o FFT)是通过奇偶序列运算近似的方法来优化计算的
对于FWT，我们可以通过最高位有无即前半长序列与后半长序列)运算近似来优化
记A_0)为序列前半段，A_1)为序列后半段
记A=A_0,A_1))
对于oplus):
FWTA)=FWTA_0+A_1),FWTA_0-A_1)))
IFWTA)=IFWTfrac {A_0+A_1}2),IFWTfrac {A_0-A_1}2)))
对于cup):
FWTA)=FWTA_0),FWTA_0+A_1)))
IFWTA)=IFWTA_0),FWTA_1-A_0)))
对于cap):
FWTA)=FWTA_0+A_1),FWTA_1)))
IFWTA)=IFWTA_0-A_1),IFWTA_1)))