【先叠个甲:内容纯属乱搞仅供娱乐,实测在洛谷会Unaccepted,抱着看乐子的心态看就行】
把两个数看成系数多项式
例一:123→3+2x+1x2123→3+2x+1x²123→3+2x+1x2 (系数[3,2,1],x代表10的幂)(系数 [3,2,1],x 代表 10 的幂)(系数[3,2,1],x代表10的幂)
例二:45→5+4x45→5+4x45→5+4x (系数[5,4])(系数 [5,4])(系数[5,4])
众所周知,两数相加 = 多项式系数对应相加
例:123+45→(3+5)+(2+4)x+1x2→8+6x+1x2123+45→(3+5)+(2+4) x+1x²→8+6x+1x²123+45→(3+5)+(2+4)x+1x2→8+6x+1x2 对应 168168168
正常直接加系数时间复杂度为 O(N)O(N)O(N),但我要想出来一个比 O(N)O(N)O(N) 更牛逼的代码,于是我想到了FFT:
时间复杂度:O(NlogN)O(N \log N)O(NlogN)
但这还是不够,我们可以继续优化为 O(N2)O(N²)O(N2)
于是乎我们可以放弃 FFT,改用离散傅里叶变换,也就是 DFT
直接算 DFT 和 逆 DFT,其复杂度就达到了 O(N2)O(N²)O(N2)
离散傅里叶变换(DFT)的定义如下:
对长度为 nnn 的序列 a[0..n−1]a[0..n-1]a[0..n−1],其 DFT 结果 A[0..n−1]A[0..n-1]A[0..n−1] 满足:
A[k]=∑j=0n−1a[j]⋅Wnjk(0≤k<n)A[k] = \sum_{j=0}^{n-1} a[j] \cdot W_n^{jk} \quad (0 \leq k < n)A[k]=∑j=0n−1 a[j]⋅Wnjk (0≤k<n)
其中:
Wn=e−2πi/nW_n = e^{-2\pi i / n}Wn =e−2πi/n
计算每个 A[k]A[k]A[k] 要遍历 nnn 个 a[j]a[j]a[j] ,做 nnn 次复数乘法和加法,要算 nnn 个 A[k]A[k]A[k]
逆离散傅里叶变换(IDFT)的定义类似,只是旋转因子变为 Wn−jkWₙ^{-jk}Wn−jk ,最后除以 nnn
为了达到 O(N2)O(N²)O(N2) 的时间复杂度,我将原代码中的 FFT 替换为 DFT/IDFT:
时间复杂度:O(N2)O(N²)O(N2)
ACGO神机:请输入文本。