题目让你求这个东西
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}就做完了。