Convolution 卷积与变换 [draft]
记录一下我见过的奇奇怪怪的卷积以及用于高效计算的变换
三月 12, 2022 · Kenshin2438
卷积积分/离散卷积
多项式卷积
异或卷积
或卷积/与卷积
SOSDP/高维前缀和
子集卷积
gcd/lcm卷积
区间卷积
卷积积分/离散卷积#
多项式卷积#
一般来说,多项式卷积表示的就是多项式乘法对应项的系数
$$ c[k] = \sum_{i+j=k}(a[i] \times b[j]) $$
FFT#
FFT 三次变两次
由于复数平方满足下式: $$ z = a + bj \rightarrow z^2=(a^2 + b^2) + 2abj $$ 我们在所