[AH/HNOI2017]礼物

\[推推公式，即求\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 <bits/stdc++.h>
# 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 <bits/stdc++.h>
# 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;
}