P3803 【模板】多项式乘法(FFT)里:
F(x)和G(x)的卷积貌似就是两多项式相乘。
在P3723 【[AH2017/HNOI2017] 礼物】里:
问题可转化为求∑i=1naibi的最大值,
题解中是这样说的:
我们把数列{a}反过来,变成∑i=1nan−i+1bi
这不是一个卷积吗~
所以把反过来的数列{a}倍长,和数列{b}卷积,得到的项里面的第n+1到n*2项的最大值,就是∑i=1naibi的最大值。
注:此题中数列a可旋转,即 1 2 3 4可变为2 3 4 1,所以倍长。
又有一篇题解提到:卷积要求两个下标加起来是常数。
但是...为什么有这个要求,卷积是什么,为什么可以求最大值?
有试着去搜了下百度,然后越来越懵了...