FFT求快速卷积的思考

ACM

离散型卷积的定义是:$$y(n)=\sum_{m=0}^{n} x(m)h(n-m)$$

注意,h函数是反转的。

在Chipher Messages一题中,b串需要反转再与a串匹配。

比如说:

a串: 110110110,则:

b`串:1011<——这里才是原来b串的头。但是向上对应到a串时,已经是m-1这个位置了。所以说,小于m-1的卷积是没有意义的。

于是,base=m。整体匹配。

同样的,比如杭电1402用FFT求A×B那一题。

可以把A串看成卷积中的x函数,而把B串的每一个字符看成h函数。那么卷积就可以看成是一个模拟乘法的过程。

因为h函数是要求逆序的,但是此时的h函数只有一个字符所以反转操作无意义。这时候的base=1。单个匹配。

估计FFT就这两种情况了。因为如果1<base<m,那么就应该直接将b串分解成若干base长度的串了。