题解 P3723 【[AH2017/HNOI2017]礼物】
HomuraCat
2019-02-27 20:12:11
似乎是一道法法塔(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);
}
```