题解 P3723 【[AH2017/HNOI2017]礼物】

似乎是一道法法塔(FFT)的套路题呢 我们首先考虑这个$+c$怎么处理 $$\sum_{i=1}^n(x_i-y_i+c)^2=nc^2+2c\sum_{i=1}^n(x_i-y_i)+\sum_{i=1}^n(x_i^2+y_i^2)-2\sum_{i=1}^n x_iy_i$$ 显然这是一个关于$c$的二次函数，最小值取 $c=-\frac{\sum_{i=1}^n(x_i-y_i)}n$ 然后发现这个展开式前面的项都很好算，就最后一项比较麻烦 我们可以把最后一项看成卷积的形式，翻转一下$b$数组，那样就可以用法法塔快速计算了 旋转操作的话就是移动$b$数列然后和$a$卷积，实现上可以把$a$数组复制一遍，然后用现在的$a$数组和$b$数组卷积，取答案中$n+1$~$2n$位的最大就行 连着爆了两次95分，原因是负小数取整需要再减1，然后c就算错了qwq，这个细节要注意的啦 ```cpp #include<bits/stdc++.h> #define N 3000005 #define fo(i, a, b) for (R int i = (a); i <= (b); ++i) #define in inline #define R register const double pi = acos(-1); int a[N], b[N], len, len1, len2, n, m; struct complex{ double real, imag; in void conj () { imag = -imag; } friend in complex operator * (const complex &x, const complex &y) { return (complex) {x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real}; } friend in complex operator + (const complex &x, const complex &y) { return (complex) {x.real + y.real, x.imag + y.imag}; } friend in complex operator - (const complex &x, const complex &y) { return (complex) {x.real - y.real, x.imag - y.imag}; } }c1[N], c2[N], omega[N]; in void dft(complex *c, int len) { int k = 0; while ((1 << k) < len) ++k; --k; fo (i, 0, len) { int g = 0; fo (j, 0, k) if ((1 << j) & i) g |= (1 << k - j); if (i < g) std::swap(c[i], c[g]); } for (int l = 2; l <= len; l <<= 1) { int mid = l >> 1; for (complex *p = c; p != c + len; p += l) for (int i = 0; i < mid; ++i) { complex tmp = omega[len / l * i] * p[mid + i]; p[mid + i] = p[i] - tmp; p[i] = p[i] + tmp; } } } inline long long flor (double x) { if (x > 0) return (long long) x; else return (long long) (x - 1.0); } int main() { scanf("%d %d", &n, &m); fo (i, 1, n) scanf("%d", &a[i]); fo (i, 1, n) scanf("%d", &b[i]); long long sum = 0, c; long long ans = 0; fo (i, 1, n) sum += a[i] - b[i]; c = flor(- 1.0 * sum / n + 0.5); fo (i, 1, n) ans += a[i] * a[i] + b[i] * b[i]; ans += 1ll * n * c * c + 1ll * 2 * c * sum; std::reverse(b + 1, b + n + 1); fo (i, 1, n) a[i + n] = a[i]; int len = 1; while (len <= n * 3) len = len << 1; fo (i, 1, n << 1) c1[i - 1].real = a[i]; fo (i, 1, n) c2[i - 1].real = b[i]; fo (i, 0, len) omega[i] = (complex) {cos(2 * pi * i / len), sin(2 * pi * i / len)}; dft(c1, len); dft(c2, len); fo (i, 0, len) c1[i] = c1[i] * c2[i]; fo (i, 0, len) omega[i].conj(); dft(c1, len); sum = 0; fo (i, n - 1, 2 * n - 1) sum = std::max(sum, (long long) ((c1[i].real + 0.5) / len)); printf("%lld", ans - sum * 2); } ```