LOJ2020 礼物

写完一次就 AC 了是我没想到的...

可以假设增加了\(c\)亮度.
即求\(\sum\limits_{i=1}^{n}(x-i-y-i+c)^2\)的最小值.
把式子展开, \(\sum\limits_{i=1}^{n}x-i^2+\sum\limits_{i=1}^{n}{y-i}^2+nc^2+2c( \sum\limits_{i=1}^{n}(x-i-y-i))-2 \sum\limits_{i=1}^{n}x-iy-i\)
可以发现前面两项是固定的.
因为c比较小, \(|c|\leq m\), 中间两项可以直接枚举\(c\).
所以只需要求出\(\sum\limits_{i=1}^{n}x-iy-i\)的最大值.
因为可以旋转, 等价于\(\sum\limits_{i=1}^{n}x_{n-i+1}y-i\).
可以看出这就是卷积的形式.
断环成链, 即求\(\sum\limits_{i=1}^{n}x_{n-i+1+k}y-i\), \(0 \leq k\leq n-1\).
所以把\(x\)翻转后,复制成两份做 fft.
第\(n+1\)到\(2n\)的系数就对应了旋转后的\(\sum\limits_{i=1}^{n}x-iy-i\).
取一个最大值就做完了.
注意数组要开大一些, 因为还要把\(x\)复制一份.
\(c\)要在\(-m\), \(m\)之间枚举, 因为展开后的式子可能是\(x-i-y-i\), 也可能是\(y-i-x-i\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef complex<double> cp; 
const int N = 6e5 + 5;
const double pi = acos(-1.0);
int n, m, len = 1, l, rev[N], x[N], y[N];
cp a[N * 2], b[N];

void fft(cp *a, int n, int inv) {
	for (int i = 0; i < n; i++) if (rev[i] < i) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k <<= 1) {
		cp wn(cos(pi / k), inv * sin(pi / k));
		for (int i = 0; i < n; i += k * 2) {
			cp w(1, 0);
			for (int j = 0; j < k; j++, w *= wn) {
				cp x = a[i + j], y = a[i + j + k] * w;
				a[i + j] = x + y, a[i + j + k] = x - y;
			}
		}
	}
	if (inv < 0) for (int i = 0; i < len; i++) a[i] /= n;
}

int main() {
	ll res = 0, dis = 0, mx = -998244353, ans = 998244353;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]), res = res + x[i] * 1ll * x[i];
    for (int i = 1; i <= n; i++) scanf("%d", &y[i]), res = res + y[i] * 1ll * y[i], dis += x[i] - y[i];
    while (len <= n * 2) len <<= 1, l++;
    for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((1 & i) << (l - 1));
    for (int i = 1; i <= n; i++) a[i].real((double)(x[n - i + 1])), b[i].real((double)(y[i]));
    for (int i = 1; i <= n; i++) a[i + n].real(a[i].real());
    fft(a, len, 1), fft(b, len, 1);
    for (int i = 0; i < len; i++) a[i] *= b[i];
    fft(a, len, -1);
    for (int i = n + 1; i <= 2 * n; i++) mx = max(mx, (ll)(a[i].real() + 0.5));
    mx *= -2;
    for (int c = -m; c <= m; c++)  ans = min(ans, n * 1ll * c * c + 2 * c * 1ll * dis);
    printf("%lld\n", res + mx + ans);
    return 0;
}