警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「HNOI 2017」礼物 - FFT

题意

传送门:洛谷 P3723 - 礼物

给你两个序列 \(A, B\)。求 \(\displaystyle\min_{0 \le j < n} \sum_{i=0}^{n-1} \left( A_i + x - B_{i+j \bmod n} \right)\)\(x\) 不给出。

\(\max\{|A_i|, |B_i|\} = m \le 100\)

解法

首先我们令 \(B'_i = B_{i+x \bmod n}\)。那么我们要求的实际上是,对于所有的 \(x\),最小的 \(\displaystyle \sum_{i=0}^{n-1} \left( A_i + x - B'_i\right)\)

将上式展开得 \(\displaystyle\sum_{i=0}^{n-1} \left( {A_i}^2 + {B'_i}^2 + x^2 + 2A_ix - 2B'_ix - 2A_iB'_i \right)\)

注意到无论 \(x\) 等于多少,\(\sum A^2\)\(\sum {B'_i}^2\) 是不变的。

因为 \(\sum \left( A_i - B'_i \right)\) 是常数,所以上式中 \(\displaystyle\sum_{i=0}^{n-1} \left( x^2 + 2A_ix - 2B'_ix \right) = nx^2 + 2x \sum_{i=0}^{n-1}\left( A_i - B'_i \right)\) 可以看做一个二次函数。

所以除了 \(\displaystyle 2\sum_{i=0}^{n-1} A_iB'_i\),其它部分都是确定的。

那么我们只要求出二次函数的最小值和最后一项的最大值,就可以把原式求出来了。

但是感觉最后一项不是很好求……

考虑令 \(A'_i = A_{n-i-1}\)。那么我们要求的就是 \(\displaystyle 2\sum_{i=0}^{n-1} A'_{n-i-1}B'_i\),这是一个卷积的形式。

所以我们将 \(A\) 反转,\(B\) 倍长,然后求新的 \(A\)\(B\) 的卷积。那么第 \(n-1\) 项到第 \(2n - 2\) 项的最大值就是最后一项的最大值。

因为 \(m \le 100\),我们可以暴力枚举 \(i \in [n-1, 2n-2], j \le [-m, m]\),然后计算贡献求最小值即可。

代码