\[推推公式，即求\Sigma^{n}_{i=1} (x_{i+k}-y_i+c)^2最小，c范围为[-m, m]\]
\[拆开，就是\Sigma x_i^2 + \Sigma y_i^2 + n * c^2 + 2*c*\Sigma(x_{i+k}-y_i) - 2*\Sigma^{n}_{i=1} x_{i+k}y_i\]\[即求2*\Sigma^{n}_{i=1} x_{i+k}y_i最大，再枚举c即可\]七十分暴力代码（暴力分贼多）
# include# define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(1e5 + 10);IL ll Read(){ char c = '%'; ll x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1; for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; return x * z;}int n, m;ll sqx, sqy, sx, sy, x[_], y[_], ans = -1e18, mn = 1e18;int main(RG int argc, RG char *argv[]){ n = Read(); m = Read(); for(RG int i = 1; i <= n; ++i) x[i + n] = x[i] = Read(), sx += x[i], sqx += x[i] * x[i]; for(RG int i = 1; i <= n; ++i) y[i] = Read(), sy += y[i], sqy += y[i] * y[i]; for(RG int i = 0; i < n; ++i){ RG ll cnt = 0; for(RG int j = 1; j <= n; ++j) cnt += x[j + i] * y[j]; ans = max(ans, cnt); } for(RG int c = -m; c <= m; ++c) mn = min(mn, 1LL * n * c * c + 1LL * 2 * c * (sx - sy) - 2 * ans); printf("%lld\n", mn + sqx + sqy); return 0;}
\[\Sigma^{n}_{i=1} x_{i+k}y_i，很套路，就往FFT上靠，把y反转不就变成\Sigma^{n}_{i=1} x_{i+k}y_{n-i+1}\]
\[这不就是卷积，就是多项式相乘后第n+k+1项的系数，这就可以FFT了\]把y反转，再倍长，跑一遍FFT，取有用的中间一段的最大值
再枚举c求解即可# include# define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(4e5 + 10);const double Pi(acos(-1));IL ll Read(){ char c = '%'; ll x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1; for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; return x * z;}struct Complex{ double real, image; IL Complex(){ real = image = 0; } IL Complex(RG double a, RG double b){ real = a; image = b; } IL Complex operator +(RG Complex B){ return Complex(real + B.real, image + B.image); } IL Complex operator -(RG Complex B){ return Complex(real - B.real, image - B.image); } IL Complex operator *(RG Complex B){ return Complex(real * B.real - image * B.image, real * B.image + image * B.real); }} A[_], B[_];int n, m, N, M, l, r[_];ll sx, sy, sqx, sqy, mx = -1e18, ans = 1e18;IL void FFT(RG Complex *P, RG int opt){ for(RG int i = 0; i < N; i++) if(i < r[i]) swap(P[i], P[r[i]]); for(RG int i = 1; i < N; i <<= 1){ RG Complex W(cos(Pi / i), opt * sin(Pi / i)); for(RG int p = i << 1, j = 0; j < N; j += p){ RG Complex w(1, 0); for(RG int k = 0; k < i; ++k, w = w * W){ RG Complex X = P[k + j], Y = w * P[k + j + i]; P[k + j] = X + Y; P[k + j + i] = X - Y; } } }}int main(RG int argc, RG char *argv[]){ n = Read() - 1; m = Read(); for(RG int i = 0; i <= n; ++i) A[i].real = Read(), sx += A[i].real, sqx += A[i].real * A[i].real; for(RG int i = n; i >= 0; --i) B[i + n + 1].real = B[i].real = Read(), sy += B[i].real, sqy += B[i].real * B[i].real; for(M = 3 * n, N = 1; N <= M; N <<= 1) ++l; for(RG int i = 0; i < N; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); FFT(A, 1); FFT(B, 1); for(RG int i = 0; i < N; ++i) A[i] = A[i] * B[i]; FFT(A, -1); for(RG int i = n; i <= 2 * n; ++i) mx = max(mx, (ll)(A[i].real / N + 0.5)); for(RG int c = -m; c <= m; ++c) ans = min(ans, 1LL * (n + 1) * c * c + 1LL * 2 * c * (sx - sy)); printf("%lld\n", ans + sqx + sqy - 2 * mx); return 0;}