关于卷积
  • 板块学术版
  • 楼主__凉皮__
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/6/26 15:41
  • 上次更新2023/10/27 22:31:40
查看原帖
关于卷积
259944
__凉皮__楼主2022/6/26 15:41

P3803 【模板】多项式乘法(FFT)里:

F(x)F(x)G(x)G(x)的卷积貌似就是两多项式相乘。

在P3723 【[AH2017/HNOI2017] 礼物】里:

问题可转化为求i=1naibi\sum_{i=1}^na_ib_i的最大值,

题解中是这样说的:

我们把数列{a}\{a\}反过来,变成i=1nani+1bi\sum_{i=1}^na_{n-i+1}b_i

这不是一个卷积吗~

所以把反过来的数列{a}\{a\}倍长,和数列{b}\{b\}卷积,得到的项里面的第n+1到n*2项的最大值,就是i=1naibi\sum_{i=1}^na_ib_i的最大值。

注:此题中数列a可旋转,即 1 2 3 4可变为2 3 4 1,所以倍长。

又有一篇题解提到:卷积要求两个下标加起来是常数。

但是...为什么有这个要求,卷积是什么,为什么可以求最大值?

有试着去搜了下百度,然后越来越懵了...

2022/6/26 15:41
加载中...