BZOJ2194 快速傅立叶之二

题目让你求这个东西

C_k=\sum_{i=k}^{n-1}{A_iB_{i-k}}

然后假设把 B 全给翻转,那么就是求

C_k=\sum_{i=k}^{n-1}{A_iB_{n-1-i+k}}

然后发现这样把次数凑起来就是与 i 无关的了,成了这样:

D_{n-1+k}=\sum_{i=k}^{n-1}{A_iB_{n-1+k-i}}

那么

\text{let }\lambda =n-1+k

就有

D_{\lambda}=\sum_{i=k}^{n-1}{A_iB_{\lambda -i}}

注意这里长的很像卷积,但是范围是不一样的,尝试把正常卷积形式的其余对应的项写出来,发现都是 0  。。

所以就可以看做卷积了,直接上 FFT 。

然后对应一下

C_0=D_{n-1} C_{n-1}=D_{2n-2}

就做完了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据