FFT求快速卷积的思考
离散型卷积的定义是：$$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长度的串了。