FFT杂谈
因为之前的我已经不想去动他了。QAQ
其实FFT并不难学，大纲是这样：
- 前置知识
- 分治
- 蝴蝶变换
- 学完了，没了
之前那个前面不是是抄你谷多项式奆佬的，后面的各种优化没什么实际意义还疯狂掉精度，基本在实战中不会去碰他，所以那篇文章我可以说是弃飞了。
FFT的前置知识并不多，向量和单位根，向量相乘的两个性质一个用相似，一个用两点距离公式爆算都能证明，也就没什么难度。
会用到的性质：
- 向量相乘模相乘
- 向量相乘辐角相加
单位根的定义百度一下，你就知道。
当然，单位根用到的性质在下面列出来了：
- \(w_{n}^0=1,w_{n}^k=w_{n}^{k\mod n}\)
- {\(x∈C\)|\(x=w_{n}^i(i∈[0,n-1],i∈Z)\)}的元素个数是\(n-1\)个（其实意思就是\(w_{n}^i\)互不相等）
- \(w_{n}^k=w_{2n}^{2k}\)
- \(w_{n}^k=-w_{n}^{k+\frac{n}{2}}(n≡0\mod2)\)
- \(\sum\limits_{i=0}^{n-1}(w_{n}^{j-k})^i=n*[j=k]\)（\([A]\)表示如果\(A\)条件成立，则\([A]=1\)，否则为\(0\)）
- \(w_{n}^k*w_{n}^t=w_{n}^{k+t}\)
只要用到这几个性质，就可以完美的推导出FFT。
这里也不展开，主要就是奇偶分治。
至于蝴蝶迭代，这个我之前的博客也就，在这里就不展开了，代码以前也是有的，我看了一下，我之前的代码长得还行(⊙﹏⊙)。
但是如果这里就这么一点东西，那我还做个P的杂谈啊(╯‵□′)╯︵┻━┻
首先，关于快速傅里叶变换，你可以觉得其很神奇，因为他巧妙的利用了单位根的性质，之前那个IDFT的推导，也很神奇，好像一气呵成似的。
当然，这里介绍一种不同的理解方式（听说卷积跟线性代数有关，但是那个我不会，就不展开了）
其实你会发现，其实DFT和IDFT就是一个\(1*n\)的矩阵乘一个\(n*n\)的矩阵的过程，所以理论上只要\(IDFT\)和\(DFT\)的矩阵互逆，这样就可以完美的相互抵消。
当然，DFT中的矩阵叫范德蒙德矩阵。
图片来自参考链接的奆佬博客Orz中
所以，这看似运气十足的FFT背后也有其科学的数学道理。
NTT
全称：快速速论变换
请注意，本文中对于一个多项式模一个整数，只是对每一个系数取模而已。
优点：
- 全是整数，不用担心掉精度的问题。
- 可以计算特定模数的卷积。
- 因为不用计算复数，所以乘法少了不少，貌似常数加快了b（￣▽￣）d 。
缺点：
- 不能计算小数，过程涉及到取模，所以一旦数域超过了模数，就难以计算。
- 模数必须是\(k*2^t+1\)的形式，且必须是一个质数。
- 由于模运算比较慢，所以常数经常不如FFT。
你是不是以为NTT十分的妙？
不，其实就是FFT的过程然后把单位根换了一个更加神奇的东西。
上面也列了，我们会利用到单位根的一些性质，但是其实只要我们能在整数中找到一个同样能满足上述性质的东西，就可以完美的换成整数啦。
当然，在一般的整数域我们很难找到满足条件的数字。
但是如果套上一个模，如果这个模有原根，则有个与原根相关的东西刚好可以满足上面。
设模为\(p\)，\(p\)是形式为\(k*2^t+1\)形式的质数，同时原根为\(g\)。
（原根定义：在模\(p\)的时候，如果对于\(n\)，\(φ(p)\)是最小的正整数 \(t\) 满足 \(n^t≡1\)，则 \(n\) 为\(p的原根\)， \(φ(p)\)表示小于\(p\)的正整数中与 \(p\) 互质的数字个数）
则我们可以把\(w_{n}^i\)替换成\(g^{\frac{p-1}{n}*i}\)（假设\(n|p-1\)），用\(g_{n}^i\)简化符号。
当然，其是否满足上面的式子，我们来看一下：
- \(g_{n}^0≡1,g_{n}^i≡g_{n}^{i\mod n}\)
证明：\(g_{n}^0≡g^0=1\)，将 \(i\) 表示成 \(kn+t(0≤t<n)\) 的形式，所以\(g_{n}^i≡g_{n}^{kn+t}≡g^{\frac{p-1}{n}*(kn+t)}≡g^{\frac{p-1}{n}*kn}*g^{\frac{p-1}{n}*t}≡g^{\frac{p-1}{n}*t}≡g_{n}^t\)，证毕，同理，因为都等于\(g_{n}^t\)，所以\(g_{n}^i≡g_{n}^{i±n}\) - {\(x∈Z\)|\(x=g_{n}^i(i∈[0,n-1],i∈Z)\)}的元素个数是\(n-1\)个（意思就是\(g_{n}^i\)互不相等）
证明：假设\(g_{n}^i≡g_{n}^j(i>j)\)
\(g^{\frac{p-1}{n}*i}≡g^{\frac{p-1}{n}}*j\)
\((g^{\frac{p-1}{n}*(i-j)}-1)*g^{\frac{p-1}{n}*j}≡0\)
那么\(p|(g^{\frac{p-1}{n}*(i-j)}-1)*g^{\frac{p-1}{n}*j}\)，但是如果\(p∤g\)，则\(p∤p^k(k∈Z^{*})\)
所以\(p|(g^{\frac{p-1}{n}*(i-j)}-1)\)
所以\(g^{\frac{p-1}{n}*(i-j)}≡1\)，这显然是不成立的，因为\(\frac{p-1}{n}*(i-j)<p-1=φ(p)\) - \(g_{n}^i≡g_{2n}^{2i}\)
证明：\(g_{n}^i≡g^{\frac{p-1}{n}*i}≡g^{\frac{p-1}{2n}*2i}\)。 - \(g_{n}^i≡-g_{n}^{i+\frac{n}{2}}(2|n)\)
证明：\(g_{n}^{i+\frac{n}{2}}≡g^{\frac{p-1}{n}*(i+\frac{n}{2})}≡g^{\frac{p-1}{n}*i}*g^{\frac{p-1}{n}*\frac{n}{2}}≡g_{n}^i*g^{\frac{p-1}{2}}=-g_{n}^i\)
当然，至于为什么\(g^{\frac{p-1}{2}}≡-1\)，我们还需要证明一个东西：
对于模质数\(p\)，\(x^2≡1\)的解只有两个\(1,-1\)（或者说是其的同余）。
\(x^2≡1\)
则\((x+1)(x-1)≡0\)，那么\(p|(x+1)\)或者\(p|(x-1)\)，所以\(x≡p+1≡1\)或\(x=p-1≡-1\)。
但是因为\(g\)是原根，所以\(g^{\frac{p-1}{2}}\)只能是\(-1\)。 - \(g_{n}^{i}*g_{n}^j≡g^{i+j}_{n}\)。
5,6点换了一个顺序，海星。
证明：展开即可，没什么好说的 - \(\sum\limits_{i=0}^{n-1}(g_{n}^{j-k})^i≡n*[j=k]\)
证明：其实完全没有什么必要证明的，反正这个东西只要用相同的性质套到FFT中便可以证明了：
先求\(\sum\limits_{i=0}^{n-1}(g_{n}^j)i\)
当\(j≠0\)时
\(\sum\limits_{i=0}^{n-1}(g_{n}^j)i≡\frac{g_{n}^{nj}-1}{g_{n}^j-1}≡0\)。
但是，如果\(j=0\)
那么显然\(\sum\limits_{i=0}^{n-1}(g_{n}^j)i≡n\)
那么什么时候\(j=0\)呢？也就是上述式子中的\(j=k\)时成立，证毕。
然后就没有什么了，直接把代码中的单位根换成\(g\)，就可以求解了，但是，仅适用于整数卷积。
当然，需要注意的是：
- \(g_{n}^i\)中\(n\)必须整除\(p-1\)，而\(FFT\)中\(n=2^i(i∈[1,r])\)，所以\(p=k*2^{t}+1\)就是这么一个道理。
- 同样的，对于补充到\(2\)的次幂的多项式长度\(len'=2^r\)，我们要求\(r<=t\)，所以对于原来的多项式长度\(len\)，我们要求\(len≤2^t\)，所以\(p\)的\(2^t\)要尽可能的大，那是最好的。
- 其次，值域的上届减下界\(+1\)要小于\(p\)，因为模\(p\)最怕的就是在值域中有两个数字同余。
- 对于\(g_{n}^i(i<0)\)，此时\(g_{n}^i≡\frac{1}{g^{\frac{p-1}{n}*(-i)}}≡(\frac{1}{g})^{\frac{p-1}{n}*(-i)}\)，所以只要求出\(g\)的逆就可以计算\(g_{n}^i(i<0)\)了，当然，\(g\)的逆也是一个原根，证明如下：
\(g'^{i}≡(g^i)'\)（其中\(x'\)表示\(x\)的逆）
而\(1\)的逆是其本身，且因为一个数不存在两个不同余的逆，所以很容易知道\(g'\)也是原根。 - 在IDFT中应当用\(g_{n}^{-i}\)替换\(w_{n}^i\)，应该不会只有我一个憨憨用\(-g_{n}^i\)去代替吧QAQ。
- 在最后输出除长度\(n\)时，需要注意的是，不能直接除\(p\)，即使值域中的每个数字都小于\(p\)，因为虽然值域的长度小于\(p\)，但是不代表要求值域的长度\(*n\)以后还小于\(p\)，所以还是乘 \(n'\) 的更加保险，当然，如果你这值域长度小的可怜，当我没说。
- 没什么好提示了，还不快去