这道题我一开始做的时候啥也不会……心想这和FFT有啥关系啊……
旁边的(mrclr)告诉我说要勇于把式子分解。然后我就把式子分解了一下。我们要求的是(sum_{i=0}^n(x_i - y_i - c)^2)，拆开之后就是(sum_{i=0}^n(x_i^2 + y_i^2 - 2x_iy_i - 2(x_i-y_i)c + c^2))
由于m的范围很小，增加（减少）的亮度可以直接枚举，然后这好像式子中只有(sum_{i=0}^nx_iy_i)不是已知的量？
这个式子的形式非常的熟悉，我们只要把其中一个的顺序倒过来，那么就变成了(sum_{i=0}^nx_{n-i}y_i),就成为了卷积的形式，可以用FFT维护。
但是现在旋转是不确定的，总不能每旋转一次都用FFT计算一次吧……
这时候旁边的(mrclr)又告诉我，其实一次FFT就可以完事。想到卷积的形式，他其实只是两段长为n的区间互相乘积的和
……那我们就像做环的题一样，先把其中一段序列倒过来并且复制一段在后面，直接拿这段长的和另一段序列卷积，最后只取合适范围内的结果就行了。
然后我写了以后数一直不对……发现自己在最后枚举c的时候忘记乘以n了……
看一下代码。PS：这题数据好像很水……我调试的时候只在正负10内枚举的竟然能过……
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;
const int M = 200005;
const ll INF = 1e15;
const double eps = 1e-7;
const double pi = acos(-1);
const ll mod = 998244353;
ll read()
{
ll ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
struct Comp
{
double x,y;
Comp(){}
Comp(double px,double py){x = px,y = py;}
fr Comp operator + (const Comp &a,const Comp &b) {return (Comp){a.x + b.x,a.y + b.y};}
fr Comp operator - (const Comp &a,const Comp &b) {return (Comp){a.x - b.x,a.y - b.y};}
fr Comp operator * (const Comp &a,const Comp &b) {return (Comp){a.x * b.x - a.y * b.y,a.y * b.x + a.x * b.y};}
}a[M<<1],b[M<<1],kx,ky;
int n,m,len = 1,L,rev[M<<1];
ll maxn,c[M<<1],suma,sumb,ans = INF;
void fft(Comp *a,int f)
{
rep(i,0,len-1) if(i < rev[i]) swap(a[i],a[rev[i]]);
for(int i = 1;i < len;i <<= 1)
{
Comp omg1(cos(pi / i),f * sin(pi / i));
for(int j = 0;j < len;j += (i << 1))
{
Comp omg(1,0);
rep(k,0,i-1)
{
kx = a[k+j],ky = omg * a[k+j+i];
a[k+j] = kx + ky,a[k+j+i] = kx - ky,omg = omg * omg1;
}
}
}
}
int main()
{
n = read() - 1,m = read();
rep(i,0,n) a[n-i].x = a[(n<<1)+1-i].x = read(),suma += (a[n-i].x * a[n-i].x),sumb += a[n-i].x;
rep(i,0,n) b[i].x = read(),suma += (b[i].x * b[i].x),sumb -= b[i].x;
//rep(i,0,(n<<1)+1) printf("%.2lf ",a[i].x);enter;
//rep(i,0,n) printf("%.2lf ",b[i].x);enter;
while(len <= n * 3) len <<= 1,L++;
rep(i,0,len-1) rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (L-1));
fft(a,1),fft(b,1);
rep(i,0,len-1) b[i] = b[i] * a[i];
fft(b,-1);
rep(i,0,len-1) c[i] = (ll)floor(b[i].x / len + 0.5);
//rep(i,0,len-1) printf("#%lld ",c[i]);enter;
//printf("$%lld %lld
",suma,sumb);
rep(i,n,2*n-1) maxn = max(maxn,c[i]);
//printf("%lld
",maxn);
rep(i,-100,100) ans = min(ans,suma - 2 * sumb * i + i * i * (n+1) - 2 * maxn);
printf("%lld
",ans);
return 0;
}