从快速傅里叶变换到各种卷积

Easy

高精度乘法

直接多项式相乘+进位

BZOJ2194

求c_k=sum_{i=k}^{n-1}a_i*b_{i-k}

把b的下标倒过来

变成

C_k=sum_{i=k}^{n-1}a_i*b_{n-i+k}

其实就是

C_{k-n}=sum_{i=k-n}^{n-1}a_i*b_{k-i}

和正常多项式乘法没有区别

BZOJ3160

Manacher+FFT

不会Manacher没写

Medium

循环卷积hihocoder 1388

即求

F[k]=2sum_{i=0}^{n-1}a_i*b_{(i+j)~mod~n}

那么这种下标有取模的循环卷积：

那么把原数列加长一倍就好了。。，其余就是上面那个翻转b的Easy Trick了

To be continue

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/chouti/p/6212762.html