Description
Solution
不难发现，将其中一个手环中所有装饰物的亮度增加一个相同的非负整数 \(c\)，可以转化成对其中一个手环增加 \(c\ (c \in Z)\)。那么最终的差异值就是：
\[\sum\limits_{i = 1}^{n}(a_i - b_i + c)^2 \]把平方拆开：
\[\sum\limits_{i = 1}^{n}a_i^2 + b_i^2 + c^2 - 2a_ib_i+ 2a_ic - 2b_ic \\ \sum\limits_{i = 1}^{n}(a_i^2 + b_i^2) + nc^2 + 2c\sum\limits_{i = 1}^{n}(a_i - b_i) - 2\sum\limits_{i = 1}^{n}a_ib_i \]我们发现，第一项是固定的，第二三项枚举一下 \(c\) 即可计算出答案，第四项看起来就很卷积。
具体来说，把 \(b\) 翻转一下，即求 \(\sum\limits_{i = 1}^{n}a_ib_{n - i + 1}\)，但是这玩意是个环，怎么办呢？经典破环为链。
把 \(a\) 翻倍，最后从 \(n + 1 \sim 2n\) 项里枚举答案即可。
Code
#include <bits/stdc++.h>
#define pi acos(-1.0)
#define eps 1e-3
#define ll long long
using namespace std;
namespace IO{
inline int read(){
int a = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
template <tbpename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 4e5 + 10;
int n, m;
ll a1, a2, b1, b2, ans = 1e18;
int p[N];
namespace FFT{
struct poly{
double x, y;
poly(double _x = 0, double _y = 0) {x = _x, y = _y;}
friend poly operator + (poly a, poly b) {return poly(a.x + b.x, a.y + b.y);}
friend poly operator - (poly a, poly b) {return poly(a.x - b.x, a.y - b.y);}
friend poly operator * (poly a, poly b) {return poly(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}
}a[N], b[N];
int lim, len;
inline void get_rev(int n){
lim = 1, len = 0;
while(lim <= n) lim <<= 1, ++len;
for(int i = 0; i <= lim; ++i) p[i] = (p[i >> 1] >> 1) | ((i & 1) << (len - 1));
}
inline void fft(poly A[], int lim, int type){
for(int i = 0; i < lim; ++i)
if(i < p[i]) swap(A[i], A[p[i]]);
for(int mid = 1; mid < lim; mid <<= 1){
poly Wn(cos(pi / mid), type * sin(pi / mid));
for(int i = 0; i < lim; i += (mid << 1)){
poly w(1, 0);
for(int j = 0; j < mid; ++j, w = w * Wn){
poly x = A[i + j], y = w * A[i + j + mid];
A[i + j] = x + y;
A[i + j + mid] = x - y;
}
}
}
if(type == 1) return;
for(int i = 0; i < lim; ++i) A[i].x = (A[i].x / lim + 0.5);
}
inline void Mul(int n, int m, poly a[], poly b[]){
get_rev(n + m);
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);
}
}
using namespace FFT;
int main(){
n = read(), m = read();
for(int i = 0; i < n; ++i) a[i].x = read(), a1 += a[i].x, a2 += a[i].x * a[i].x;
for(int i = n - 1; i >= 0; --i) b[i].x = read(), b1 += b[i].x, b2 += b[i].x * b[i].x;
for(int i = 0; i < n; ++i) a[i + n].x = a[i].x;
Mul(n << 1, n, a, b);
for(int i = 1; i <= n; ++i)
for(int j = -m; j <= m; ++j)
ans = min(ans, a2 + b2 + n * j * j + 2ll * (a1 - b1) * j - 2 * (ll)a[i + n].x);
write(ans), puts("");
return 0;
}