复数

复数的表示

形如\(a+bi\)的实数成为复数
a称为实部，b称为虚部，i为虚数单位(\(i=\sqrt{-1}\))

以\(R\)(实部)为\(x\)轴，以\(i\)(虚部)为\(y\)轴
可以将一个复数表示为该二维平面内的一个向量

复数的模长和辅角

复数的模长即对应向量的模长\(r=\sqrt{a^2+b^2}\)
辅角\(arg\)为该向量与\(x\)轴正半轴的夹角
(辅角有无限多个，每个相差\(2k\pi,k\in Z\))
那么\(a=r\cos \arg~,b=r\sin \arg\)
则\(a+bi=r(\cos \arg+i\sin \arg)\)

复数的加法

\((a+bi)+(c+di)=(a+c)+(b+d)i\)
可以看做是该二维平面中向量的加法
满足三角形法则和平行四边形法则

复数的乘法

记\(x=a+bi=r(\cos p+i\sin p)\)，\(y=c+di=t(\cos q+i\sin q)\)
\[ \begin{aligned} xy&=rt(\cos p\cos q-\sin p\sin q+i(\cos p\sin q+\sin p\cos q))\\ &=rt(\cos(p+q)+i\sin(p+q)) \end{aligned} \]
因此有
\(|xy|=|x||y|\)
\(\arg(xy)=\arg(x)+\arg(y)\)

复数的n次根

\(x=a+bi=r(\cos p+i\sin p)\)
\(x^{\frac 1 n}\)表示满足\(y^n=x的所有y\)
根据乘法的性质可知
\(y=r^{\frac 1 n}\left(\cos\frac{p+2k\pi}{n}+i\sin\frac {p+2k\pi}{n}\right)\)
可知当\(k=0\dots n-1\)时，\(y\)表示不同的\(n\)个复数
即一个数的\(n\)次单位根有\(n\)个
几何意义上，它们组成圆内接的一个正\(n\)边形

n次单位根

定义\(r=1,\arg=0\)时即复数等于实数\(1\)时
复数的n次根为n次单位根
n次单位根\(x\)满足
\(x=r\left(\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}\right)\)

可知\(n\)次单位根在复数平面的单位圆上，把圆\(n\)等分
且\(n\)个\(n\)次单位根组成\(n\)次单位根群(乘群)
将群中的生成元记作本原单位根
取其中一个记为\(\omega_n\)
一般选\(\omega_n=\cos \frac {2\pi}{n}+i\sin\frac{2\pi}{n}\)
根据欧拉公式 \(e^{ix}=\cos x+i\sin x\)
则\[\omega_n=e^\frac {2\pi~i}{n}\]
可以用\(\omega_n^k,k=0\dots n-1\)来表示其它的\(n\)个单位根

n次单位根的性质

\(\omega_n^k=e^{\frac {2k\pi i} n}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{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^{i\pi}\omega_n^k=-\omega_n^k\)（几何理解：转半个圆）
\(\frac 1 n\sum_{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\)）

形式幂级数

\[F(x)=\sum_{i=0}^n f_ix^i\]

基本记号

\((F+G)(x)=\sum_{i=0}^n(f_i+g_i)x^i\)
\((F\times G)(x)=\sum_{i=0}^{2n}\left(\sum_{j+k=i}f_jg_k\right)x^i\)
\(F\cdot G\)或\(FG\)表示点乘（对应位相乘）
\(F^n(x)=\prod_{i=1}^n F(x)\)
\(\deg F\)表示\(F\)的最高次数
没有声明的情况下，大写字母表示多项式，对应小写字母表示该多项式的系数

定义乘法

即多项式乘法
就是上面的\(F\times G\)啦

运算律

乘法满足结合率，交换律，对加法的分配率

复数域卷积

DFT的推导

利用一个if语句\(\frac 1 n\sum_{i=0}^{n-1} \omega_n^{ki}=[k~mod~n=0]\)

设\(C=A\times B\)
则
\[ \begin{aligned} c_k&=\sum_{i+j=k} a_ib_j\\ &=\sum_i\sum_j[i+j=k]a_ib_j\\ &令n为一个比(\deg A+\deg B)大的数\\ &=\sum_i\sum_j[i+j\equiv k(mod~n)] a_ib_j\\ &=\sum_i\sum_j[(i+j-k)~mod~n=0]a_ib_j\\ &=\sum_i\sum_j\frac 1 n\sum_{l=0}^{n-1}\omega_n^{(i+j-k)l} a_ib_j\\ &=\frac 1 n\sum_{l=0}^{n-1}\omega_n^{-kl}\left(\sum_i\omega_n^{il}a_i\right)\left(\sum_j\omega_n^{jl}b_j\right)\\ &=\frac 1 n\sum_{l=0}^{n-1}\omega_n^{-kl} A(\omega_n^l)B(\omega_n^l)\\ \end{aligned} \]
DFT可以看做求点值
IDFT可以看做插值(我们之前令\(n\)为\(比\deg A+\deg B=\deg C\)大的数)

DFT的性质

\(DFT[i](A)=\sum_{j=0}^{n-1} a_j\omega_n^{ij}=A(w_n^i)\)
\(IDFT[i](A)=\frac 1 n\sum_{j=0}^{n-1}a_j\omega_n^{-ij}\)

1.\(DFT(k_1A+k_2B)=k_1DFT(A)+k_2DFT(A)\)
2.\(DFT(A\times B)=DFT(A)\cdot DFT(B)\)
3.\(A=IDFT(DFT(A))\)

FFT优化

\[ \begin{aligned} &当k\le n/2时\\ A(\omega_n^k)&=A_0(\omega_n^{2k})+\omega_n^kA_1(\omega_n^{2k})\\ &=A_0(\omega_{n/2}^k)+\omega_n^kA_1(\omega_{n/2}^k)\\\\ &当k\gt n/2时\\ A(\omega_n^k)&=A_0(\omega_n^{2k})+\omega_n^kA_1(\omega_n^{2k})\\ &=A_0(\omega_{n/2}^k)+\omega_n^kA_1(\omega_{n/2}^k)\\ &=A_0(\omega_{n/2}^{k-n/2})-\omega_n^{k-n/2}A_1(\omega_{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，这样递归计算
最后的式子称蝶形运算
总复杂度是\(T(n)=2T(n/2)+O(n)\)的
根据主定理\(T(n)=O(n\log n)\)
逆运算的式子长得差不多，处理也是同理的

具体实现网上很多本文不细说

mod P域卷积

模数为质数
所以该环是一个域（有单位元1，且除非零元外有逆元）
\(1\)的\(P-1\)次单位根是满足之前单位根的性质的（满足下标是整数的条件下）
设\(P-1=2^m*C\)
当\(2^m\)比\(\deg C\)大时
我们就可以用原根来替代\(\omega\)

判断原根与寻找原根

bool ok(LL x,int p)
{//类似某题分解质因数判原根的方法，单次log
    int l=p-1,i,L=p-1;//根据欧拉，p以内的最长循环节为p-1
    for(i=2;i*i<=l;i++) if(l%i==0){
        if(pwd(x,L/i,p)==1) return 0;
        while(l%i==0) l/=i;
    }
    if(l>1&&pwd(x,L/l,p)==1) return 0;
    return 1;
}
 
LL getrt(int p)
{
    if(p==2) return 1;
    int res=2;
    for(;!ok(res,p);res++);
    return res;
}

NTT

数论变换
不同于\(\omega_n=]cos(2\pi/n)+i\sin(2\pi/n)\)可以直接计算
NTT实现的时候要预处理\(g_n\)，不然每次快速幂算总复杂度\(O(n\log^2n)\)
NTT的性质与FFT相同，具体实现上网找

其它域上的卷积

待补多项式导论

集合幂级数

\[F(x)=\sum_{s\in 2^U}f_sx^s\]

基本记号

\(U=\{1\cdots n\}\),代表本文的全集
记\(2^X\)表示集合\(X\)的幂集，即所有\(X\)的子集组成的集合
记\(s_x\)表示集合s的二进制第x位
\(|s|\)表示bitcount(x)

在\(F(x)=\sum_{s\in 2^U}f_sx^s\)式子中
\(f_s表示第s项系数，f_sx^s没有乘法的意思，x^s代表是第s项\)
\(e.g.~~F(x)=5x^{\phi}+9x^{\{1\}}+3x^{\{1,2\}}\)
表示\(f_{\phi}=5,f_{\{1\}}=9,f_{\{1,2\}}=3\)

乘法定义

注意学会类比
我们希望乘法也满足结合律，交换率，对加法的分配率
常见的几种乘法：对称差\(\oplus\)，并\(\cap\)，或\(\cup\)
对于集合幂级数\(A,B\)
\((A\cup B)(x)=\sum_{k\in 2^U}\left(\sum_{i\cup j=k}a_ib_j\right)x^k\)
\((A\cap B)(x)=\sum_{k\in 2^U}\left(\sum_{i\cap j=k}a_ib_j\right)x^k\)
\((A\oplus B)(x)=\sum_{k\in 2^U}\left(\sum_{i\oplus j=k}a_ib_j\right)x^k\)

FWT的推导

复数有一个\(if\)语句性质，这边也找一个？
\((x-1)^n=\sum_{i=0}^n\binom n i(-1)^i x^{n-i}\)
所以\((1-1)^n=\sum_{i=0}^n\binom n i(-1)^i=[n=0]\)
推广一下得到
\[ \begin{aligned} &\frac 1 {2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}=[S=\phi](1)\\ &\sum_{T\subseteq X\subseteq S}(-1)^{|S|-|X|}=[T=S](2)\\ &\sum_{T\supseteq X\supseteq S}(-1)^{|X|-|S|}=[T=S](3)\\ \end{aligned} \]

（注：除了下面推导的式子以外，不排除有其它形式的FWT式子，合理即可）

于是我们以\(\oplus\)为例推导
设\(C=A\oplus B\),使用if语句(1)
\[ \begin{aligned} C_k&=\sum_{i\in 2^U}\sum_{j\in 2^U}[i\oplus j\oplus k=\phi]a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in 2^U}\frac 1 {2^n}\sum_{l\in 2^U}(-1)^{|(i\oplus j\oplus k)\cap l|} a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in 2^U}\frac 1 {2^n}\sum_{l\in2^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_{l\in2^U}(-1)^{|k\cap l|}\left(\sum_{i\in2^U}(-1)^{|i\cap l|}a_i\right) \left(\sum_{j\in 2^U}(-1)^{|j\cap l|}b_j\right) \end{aligned} \]
另外两个运算的推导可以先自己尝试推一推

设\(C=A\cup B\),使用if语句(2)
\[ \begin{aligned} C_k&=\sum_{i\in2^U}\sum_{j\in 2^U} [i\cup j=k]a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in2^U}\sum_{(i\cup j)\subseteq l\subseteq k}(-1)^{|k|-|l|} a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in2^U}\sum_{l\subseteq k}(-1)^{|k|-|l|}[(i\cup j)\subseteq l]a_ib_j\\ &因为[i\cup j\subseteq l]\Leftrightarrow [i\subseteq l][j\subseteq l]\\ &=\sum_{l\subseteq k}(-1)^{|k|-|l|}\left(\sum_{i\subseteq l}a_i\right)\left(\sum_{j\subseteq l} b_j\right)\\ \end{aligned} \]
设\(C=A\cap B\),使用if语句(3)
\[ \begin{aligned} C_k&=\sum_{i\in2^U}\sum_{j\in 2^U} [i\cap j=k]a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in2^U}\sum_{(i\cup j)\supseteq l\supseteq k}(-1)^{|l|-|k|} a_ib_j\\ &=\sum_{i\in2^U}\sum_{j\in2^U}\sum_{l\supseteq k}(-1)^{|l|-|k|}[(i\cap j)\supseteq l]a_ib_j\\ &因为[i\cap j\supseteq l]\Leftrightarrow [i\supseteq l][j\supseteq l]\\ &=\sum_{l\supseteq k}(-1)^{|l|-|k|}\left(\sum_{i\supseteq l}a_i\right)\left(\sum_{j\supseteq l} b_j\right)\\ \end{aligned} \]

FWT的性质

不证了也不难证
\(FWT(k_1A+k_2B)=k_1FWT(A)+k_2FWT(B)\)
\(FWT(A\oplus B)=FWT(A)\cdot FWT(B)\)
\(A=IFWT(FWT(A))\)

FWT的优化

注意到\(DFT\to FFT\)是通过奇偶序列运算近似的方法来优化计算的
对于FWT，我们可以通过最高位有无(即前半长序列与后半长序列)运算近似来优化
记\(A_0\)为序列前半段，\(A_1\)为序列后半段
记\(A=(A_0,A_1)\)
对于\(\oplus\):
\(FWT(A)=(FWT(A_0+A_1),FWT(A_0-A_1))\)
\(IFWT(A)=(IFWT(\frac {A_0+A_1}2),IFWT(\frac {A_0-A_1}2))\)
对于\(\cup\):
\(FWT(A)=(FWT(A_0),FWT(A_0+A_1))\)
\(IFWT(A)=(IFWT(A_0),FWT(A_1-A_0))\)
对于\(\cap\):
\(FWT(A)=(FWT(A_0+A_1),FWT(A_1))\)
\(IFWT(A)=(IFWT(A_0-A_1),IFWT(A_1))\)