多维卷积

异或卷积的本质就是 \(n\) 维循环卷积。

二维卷积

可以理解为对于二维数组 \(f\) 和二维数组 \(g\) 求二维数组 \(h\) ：

\[h_{i,j} = \sum_{a+b=i} \sum_{c+d=j} f_{a,c} \times g_{b,d}\]

这个 \(h\) 就是 \(f\) 和 \(g\) 的二维卷积。

构造生成函数数组 \({F_i}, {G_i}, {H_i}\) ，满足 \(F_i = \sum_{j} f_{i,j} x^j\) ，类似地定义 \({G_i}\) 和 \({H_i}\) ，那么有：

\[H_i = \sum_{a+b=i} F_a \times G_b\]

其中 \(F_a \times G_b\) 就是多项式卷积。

不妨把 \(F, G, H\) 的每一位所对应的多项式看做普通的元素，那么 \(H\) 就是 \(F\) 和 \(G\) 的卷积，傅里叶变换在这里仍然是可以定义的。

高维卷积

二维卷积的做法完全可以推广到高维卷积，对于两个从向量到数的映射 \(F, G\) ，定义其卷积 \(H\) 满足：

\[H_c = \sum_{a+b=c} F_a \times G_b\]

其中 \(a, b, c\) 都是高维向量。

事实上异或卷积就是一个高维卷积（循环卷积），每一维的长度都是二，根据异或卷积的实现不难推广到所有高维卷积的实现。