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

Nemlit

2019-10-10 11:59:20

Solution

~~被某大佬指出这是多项式板子!?~~ 我们假设我们原始数列是$a_i, c_i$, 旋转后的数列是$a_i, b_i$,我们的增加量为x $$\sum_{i = 1}^n(a_i - b_i + x)^2$$ 拆开平方得: $$\sum_{i = 1}^na_i^2+b_i^2+x^2+2*x*a_i-2*x*b_i-2*a_i*b_1$$ 把这些东西分下类: $$x^2*n+(\sum_{i=1}^na_i^2+b_i^2)+2*x*(\sum_{i = 1}^n a_i+b_i)+2*(\sum_{i = 1}^na_i*b_i)$$ 发现$x$只有$[-100, 100]$,我们考虑枚举x,然后就只有最后一堆是未知的 我们考虑怎么求最后一堆:两个值乘在一起的和,是不是和多项式有关系呢? 但这并不是一个卷积的形式,但我们考虑把b反向,原式就变成了:$\sum_{i=1}^na_i*b_{n-i+1}$ 于是我们就可与愉快的用多项式来做这道题了。[不会多项式?戳戳看?](https://www.cnblogs.com/bcoier/p/11644303.html) 把a数组倍长,把b数组反向,于是这道题的式子就成了:$\sum_{i=1}^na_{i+k}c_{n-i+1}$,然后多项式的第$n+1-2*n$就分别代表$k$取$0-n-1$的值了 ## $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define int long long const double pi = acos(-1); #define inf 12345678900000000 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define maxn 300005 struct node { double x, y; }a[maxn], b[maxn]; il node operator + (node a, node b) { return (node){a.x + b.x, a.y + b.y}; } il node operator - (node a, node b) { return (node){a.x - b.x, a.y - b.y}; } il node operator * (node a, node b) { return (node){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; } int n, m, lim, r[maxn], ans = inf, sum1, sum2, Ans = -inf; il void FFT(node *a, int f, int len) { rep(i, 0, len - 1) if(r[i] > i) swap(a[r[i]], a[i]); for(re int mid = 1; mid < len; mid <<= 1) { node base = (node){cos(pi / mid), f * sin(pi / mid)}; for(re int p = mid * 2, j = 0; j < len; j += p) { node w = (node){1, 0}; for(re int k = 0; k < mid; ++ k, w = w * base) { node x = a[j + k], y = a[j + k + mid] * w; a[j + k] = x + y, a[j + k + mid] = x - y; } } } } signed main() { n = read(), m = read(); rep(i, 1, n) a[i].x = a[i + n].x = read(); rep(i, 1, n) b[n - i + 1].x = read(); rep(i, 1, n) sum1 += a[i].x * a[i].x + b[i].x * b[i].x, sum2 += a[i].x - b[i].x; while((1 << lim) <= 3 * n) ++ lim; rep(i, 0, (1 << lim)) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1)); FFT(a, 1, (1 << lim)), FFT(b, 1, (1 << lim)); rep(i, 0, (1 << lim)) a[i] = a[i] * b[i]; FFT(a, -1, (1 << lim)); rep(x, -m, m) ans = min(ans, x * x * n + sum1 + 2 * x * sum2); rep(i, n + 1, 2 * n) Ans = max(Ans, (int)(a[i].x / (1 << lim) + 0.5)); printf("%lld", ans - 2 * Ans); return 0; } ```