Description
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手 环的 i 号位置装饰物亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： \sum_{i=1}^{n}(x_i-y_i)^2麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？
Input
输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始 亮度小于等于m。
接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时 针方向上各装饰物的亮度。
1≤n≤50000, 1≤m≤100, 1≤ai≤m
Output
输出一个数，表示两个手环能产生的最小差异值。
注意在将手环改造之后，装饰物的亮度 可以大于 m。
Sample Input
5 6
1 2 3 4 5
6 3 3 4 5
1 2 3 4 5
6 3 3 4 5
Sample Output
1
【样例解释】
需要将第一个手环的亮度增加1，第一个手环的亮度变为： 2 3 4 5 6 旋转一下第二个手环。对于该样例，是将第二个手环的亮度6 3 3 4 5向左循环移动 2017-04-15 第 6 页，共 6 页 一个位置，使得第二手环的最终的亮度为：3 3 4 5 6。 此时两个手环的亮度差异值为1。
正解：$FFT$。
考场上切了这题，还是很高兴的。。
首先我们可以发现，一个手环最多$+m$，我们只要分别枚举每个手环加多少就行了。
我们只考虑$x$手环加数，因为$y$手环与$x$手环其实是一样的。
枚举$m$，那么$Ans=\sum_{i=1}^{n}(x_{i}+m-y_{i})^{2}$。我们把它拆开以后可以发现，$Ans=\sum_{i=1}^{n}(x_{i}+m)^{2}+y_{i}^{2}-2*y_{i}*x_{i}-2*y_{i}*m$。
容易发现，$2*x_{i}*y_{i}$是复杂度的瓶颈。其实这一项可以很容易看出是一个卷积，我们把另一个数组翻转一下，就能发现$\sum_{i=1}^{n}x_{i}*y_{i}$是一个卷积的形式，然后直接上$FFT$就能过了。
其实这题还有复杂度更优的$O(nlogn+n)$的做法，似乎是用二次函数的最值？？不过$O(nlogn+nm)$也能过。。
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define inf (2147483647)
#define N (100010)
#define il inline
#define RG register
#define ll long long
#define C complex <long double> using namespace std; const long double pi=acos(-1.0); int a[N],b[N],n,m; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} namespace brute{ int ans,res1,res2; il void work(){
ans=inf;
for (RG int i=;i<=n;++i) a[i]=gi(),a[n+i]=a[i],res1+=a[i]*a[i];
for (RG int i=;i<=n;++i) b[i]=gi(),b[n+i]=b[i],res2+=b[i]*b[i];
for (RG int k=;k<=m;++k){
for (RG int i=;i<=n;++i) a[i]+=k;
for (RG int i=;i<=n;++i){
RG int res=;
for (RG int j=;j<=n;++j) res+=(a[j]-b[i+j-])*(a[j]-b[i+j-]);
ans=min(ans,res);
}
for (RG int i=;i<=n;++i) a[i]-=k;
}
for (RG int k=;k<=m;++k){
for (RG int i=;i<=n;++i) b[i]+=k;
for (RG int i=;i<=n;++i){
RG int res=;
for (RG int j=;j<=n;++j) res+=(b[j]-a[i+j-])*(b[j]-a[i+j-]);
ans=min(ans,res);
}
for (RG int i=;i<=n;++i) b[i]-=k;
}
printf("%d\n",ans); return;
} } namespace cheat{ C A[*N],B[*N];
int rev[*N],NN,lg;
ll r1[N],r2[N],res1,res2,tot1,tot2,ans; il void fft(C *a,RG int n,RG int f){
for (RG int i=;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]);
for (RG int i=;i<n;i<<=){
C wn(cos(pi/i),sin(f*pi/i)),x,y;
for (RG int j=;j<n;j+=(i<<)){
C w(,);
for (RG int k=;k<i;++k,w*=wn){
x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
return;
} il void work(){
for (RG int i=;i<=n;++i){
a[i]=gi(),A[i]=a[i];
res1+=a[i]*a[i],tot1+=a[i];
}
for (RG int i=;i<=n;++i){
b[i]=gi(),B[n-i+]=b[i];
res2+=b[i]*b[i],tot2+=b[i];
}
for (NN=;NN<=(n<<);NN<<=) lg++; ans=1LL<<;
for (RG int i=;i<NN;++i) rev[i]=rev[i>>]>>|((i&)<<(lg-));
fft(A,NN,),fft(B,NN,);
for (RG int i=;i<NN;++i) A[i]*=B[i]; fft(A,NN,-);
for (RG int i=n+;i<=(n<<);++i){
r1[i-n]=(ll)(A[i].real()/NN+0.5);
r1[i-n]+=(ll)(A[i-n].real()/NN+0.5);
}
memset(A,,sizeof(A)),memset(B,,sizeof(B));
for (RG int i=;i<=n;++i) A[n-i+]=a[i],B[i]=b[i];
fft(A,NN,),fft(B,NN,);
for (RG int i=;i<NN;++i) B[i]*=A[i]; fft(B,NN,-);
for (RG int i=n+;i<=(n<<);++i){
r2[i-n]=(ll)(B[i].real()/NN+0.5);
r2[i-n]+=(ll)(B[i-n].real()/NN+0.5);
}
for (RG ll k=;k<=m;++k){
RG ll cnt=res2;
for (RG int i=;i<=n;++i) cnt+=(a[i]+k)*(a[i]+k);
for (RG int i=;i<=n;++i) ans=min(ans,cnt-*(r1[i]+tot2*k));
}
for (RG ll k=;k<=m;++k){
RG ll cnt=res1;
for (RG int i=;i<=n;++i) cnt+=(b[i]+k)*(b[i]+k);
for (RG int i=;i<=n;++i) ans=min(ans,cnt-*(r2[i]+tot1*k));
}
printf("%lld\n",ans); return;
} } il void work(){
n=gi(),m=gi();
if (n<= && m<=){ brute::work(); return; }
cheat::work(); return;
} int main(){
freopen("gift.in","r",stdin);
freopen("gift.out","w",stdout);
work();
return ;
}