题意

给出循环节长度为 $n$ 的数组 $a, b$，求

$$ \min_{c,k}\left\{\sum_{i = 1}^n (c + a_{i + k} - b_i)^2\right\} $$

$1 \leqslant n \leqslant 2e5, 1 \leqslant a_i, b_i \leqslant 100$。

算法

(FFT) $O(n\log n)$

将原式展开有

$$ \sum_{i = 1}^n (c + a_{i + k} - b_i)^2 = nc^2 + 2c\sum_{i = 1}^n (a_i - b_i) + \sum_{i = 1}^n (a_i^2 + b_i^2) - 2\sum_{i = 1}^n a_{i + k}b_i $$

容易求出 $c$，只需要再求出

$$ \max_k \left\{ \sum_{i = 1}^n a_{i + k}b_i \right\} $$

设 $t_i = a_{n - i}$,则

$$ \sum_{i = 1}^n a_{i + k}b_i = \sum_{i = 1}^n t_{n - k - i}b_i $$

则 $k$ 对应的值为 $t$ 和 $b$ 的循环卷积的第 $n - k$ 项，取最大值即可。