[HNOI2017]礼物_牛客博客

[HNOI2017]礼物

我们要使 $\sum\limits_{i = 1} ^{n} (a_i - u_i) ^ 2\\$ 最小，我们能对两个序列进行一些操作。

对 $a$ 序列的 $+c_1$ 操作，我们得到 $\sum\limits_{i =1} ^{n}(a_i + c_1 - u_i) ^ 2$ 。

对 $u$ 序列的 $+c_2$ 操作，我们得到 $\sum\limits_{i = 1} ^{n} (a_i + c_1 - u_i - c_2) ^ 2$ 。

有 $从= c_1 + c_2 \in[-m, m]$ ，得到 $\sum\limits_{i = 1} ^{n} (a_i - u_i + c) ^ 2$
$ $\sum_{i = 1} ^{n} (a_i - u_i + c) ^ 2\\ \sum_{i = 1} ^{n} (a_i ^ 2 + u_i ^ 2 + 2 a_ic - 2 u_i c + c ^ 2 - 2 a_i u_i)\\ \sum_{i = 1} ^{n}(a_i ^ 2 + u_i ^ 2) + 2 (\sum_{i = 1} ^{n} a_i - \sum_{i = 1} ^{n} u_i)c + c ^ 2 - 2 \sum_{i = 1} ^{n} a_i b_i\\$ $我们发现无论对$ a, u $序列如何转动$ $\sum\limits_{i = 1} ^{n} (a_i ^ 2 + u_i ^ 2)$ 一定是一个定值，

$2 (\sum\limits_{i = 1} ^{n} a_i - \sum\limits_{i = 1} ^{n} u_i)c + c ^ 2 = Ac + c ^ 2$ ，其中 $A$ 也一定是一个定值，然后这就是一个开口向上的二次函数有极小值，可分类讨论求得，

接下来我们考虑如何求解 $\sum\limits_{i = 1} ^{n} a_i u_i$ 的最大值了

由于我们可以对其中任意的一个串循环移动，假设我们对 $u$ 逆时针移动 $t$ 次，上式就变成了 $\sum\limits_{i = 1} ^{n} a_i u_{i + t}$ 。

要是 $i + i + t$ 是一个定值就好了，这就是多项式相乘的某一项，我们就能通过 $FFT$ 求解，从这一点出发，我们构造 $i + x + i + t$ 为一个常数。

另 $x = n - 2 \times i + 1$ ，有 $i + x = n - i + 1$ ，上式有 $\sum\limits_{i = 1} ^{n} a_{n - i + 1} u_{i + t}$ ， $n + i + 1 + i + t = n + 1 + t$ ，

对于确定的 $t$ ，这就是一个多项式相乘的某一项了，我们把数组 $u$ 加倍，然后求一次 $FFT$ 就能得到所有 $t$ 的答案了，

当然为了运算方遍我们得提前把 $a$ 数组给翻转一下。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const double pi = acos(-1.0);

const int N = 1e6 + 10;

struct Complex {
  double r, i;

  Complex(double _r = 0, double _i = 0) : r(_r), i(_i) {}

}a[N], b[N];

Complex operator + (const Complex & a, const Complex & b) {
  return Complex(a.r + b.r, a.i + b.i);
}

Complex operator - (const Complex & a, const Complex & b) {
  return Complex(a.r - b.r, a.i - b.i);
}

Complex operator * (const Complex & a, const Complex & b) {
  return Complex(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}

int r[N];

void fft(Complex * f, int lim, int rev) {
  for (int i = 0; i < lim; i++) {
    if (r[i] < i) {
      swap(f[i], f[r[i]]);
    }
  }
  for (int i = 1; i < lim; i <<= 1) {
    Complex wn = Complex(cos(pi / i), rev * sin(pi / i));
    for (int p = i << 1, j = 0; j < lim; j += p) {
      Complex w = Complex(1, 0);
      for (int k = 0; k < i; k++, w = w * wn) {
        Complex x = f[j + k], y = w * f[i + j + k];
        f[j + k] = x + y, f[i + j + k] = x - y;
      }
    }
  }
  if (rev == -1) {
    for(int i = 0; i < lim; i++) {
      f[i].r /= lim;
    }
  }
}

void get_r(int lim) {
  for (int i = 0; i < lim; ++i) {
    r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ll ans = 0, res = 0;
  int n, m, lim = 1;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%lf", &a[n - i + 1].r); 
  }
  for (int i = 1; i <= n; i++) {
    scanf("%lf", &b[i].r);
    b[i + n]= b[i];
  }
  for (int i = 1; i <= n; i++) {
    ans += a[i].r * a[i].r + b[i].r * b[i].r;
    res += a[i].r - b[i].r;
  }
  ll c1 = floor(res * 1.0 / n), c2 = ceil(res * 1.0 / n);
  ans += min(n * c1 * c1 - 2 * c1 * res, n * c2 * c2 - 2 * c2 * res);
  n <<= 2;
  while (lim < n) lim <<= 1;
  n >>= 2;
  get_r(lim);  
  fft(a, lim, 1);
  fft(b, lim, 1);
  for (int i = 0; i < lim; i++) {
    a[i] = a[i] * b[i];
  }
  fft(a, lim, -1);
  res = 0;
  for (int i = 1; i <= n; i++) {
    res = max(res, ll(a[i + n].r + 0.5));
  }
  printf("%lld\n", ans - 2 * res);
  return 0;
}