Convolution 卷积与变换  [draft]

卷积积分/离散卷积 多项式卷积 一般来说,多项式卷积表示的就是多项式乘法对应项的系数 $$ c[k] = \sum_{i+j=k}(a[i] \times b[j]) $$ FFT FFT 三次变两次 由于复数平方满足下式: $$ z = a + bj \rightarrow z^2=(a^2 + b^2) + 2abj $$ 我们在所用的复数数组,其实部和虚部分别为两多项式的系数,然后平方取虚部的一半即可得到答案,此时只要一次DFT和一次IDFT。 NTT $$ c[k] = \sum_{i+j=k}(a[i] \times b[j]) \bmod P $$ $P=r\times 2^k+1$为一个素数,$g$为模$P$的原根。 MTT 任意模数NTT,考虑的是没有原根的情况。 异或卷积 $$ c[k] = \sum_{i \oplus j = k}(a[i] \times b[j]) $$ FWT 或卷积/与卷积 OR $$ c[k] = \sum_{i | j = k}(a[i] \times b[j]) $$...

March 12, 2022 · 1 min · Kenshin2438