「AHOI / HNOI 2017」礼物（生成函数 + 多项式）

题目大意

「AHOI / HNOI 2017」礼物（Luogu 3723）

有两个长度为 $n$ 的手环，每个位置上的亮度分别为 $x_1, x_2, \cdots, x_n$ 和 $y_1, y_2, \cdots, y_n$，它们都是 $[1, m]$ 中的整数。你可以给某个手环整体加上 $c$（整数），并将它旋转（循环位移）$k$ 位，然后使得 $\sum_{i = 1}^{n} (x_i - y_i) ^ 2$ 最小。

数据范围：$n \le 5 \times 10^4, 1 \le m \le 100$。

思路分析

我们先假设手环已经旋转完成，我们考虑如何选择最好的 $c$。可以发现：

$$\begin {align} \sum (x_i - y_i + c)^2 &= \sum c^2 + (2 \times \sum x_i - y_i) \times c + \sum (x_i - y_i) ^ 2 \\ &= nc^2 + (2 \times \sum x_i - y_i) \times c + (\sum x_i^2 + y_i^2) - 2 \sum x_iy_i \end {align}$$

和 $c$ 相关的是一个二次函数，其中二次项和一次项都为定值，所以我们可以求出二次函数的最小值。常数项中前面一项也是定值，而后面一项会变化，于是我们只要找到后面一项的最小值即可。换而言之，我们要找到进行循环移位后最小的：

$$\sum_{i = 1}^{n} x_iy_i$$

考虑对于每个 $k$ 算出上式。发现这是一个卷积的变形形式，我们只需将一个数组翻转，另一个数组倍长后做一次卷积即可。那么通过 FFT，可以将复杂度做到 $O(n \log n)$。

代码实现

#include <cmath>