强省HN弱省HA……（读作强省湖南弱省蛤
原题：
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一
个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突
然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有
装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，
但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差
异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，
其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手 环的 i 号位置装饰物
亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： sum_{i=1}^{n}(x_i-y_i)^2麻烦你帮他
计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？
1≤n≤50000, 1≤m≤100, 1≤ai≤m
FFT嘛，直接推公式
然后可以发现两边的项都可以o(n)预处理使得在枚举c后可以O(1)计算，中间的是个循环卷积
枚举c和k后FFT即可
代码（还没写
现在写了：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define ll long long 8 const ll inf=(ll)(1<<30); 9 int rd(){int z=0,mk=1; char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} 11 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 12 return z*mk; 13 } 14 int wtp=0,wtc[32]; 15 void wt(int x,char y){ 16 if(!x){ putchar('0'); return ;} 17 if(x<0) putchar('-'),x=-x; 18 while(x) wtc[++wtp]=x%10+'0',x/=10; 19 while(wtp) putchar(wtc[wtp--]); 20 putchar(y); 21 } 22 struct cp{ 23 double r,i; 24 cp(double _r=0,double _i=0): r(_r),i(_i){} 25 cp operator+(cp x){return cp(r+x.r,i+x.i);} 26 cp operator-(cp x){return cp(r-x.r,i-x.i);} 27 cp operator*(cp x){return cp(r*x.r-i*x.i,r*x.i+i*x.r);} 28 }; 29 int n,m; ll S=0,s=0; 30 cp a[410000],b[410000],tmp[410000],_x,_y,c[410000]; 31 int rvs[410000],dg[32],N,L; 32 void fft(cp x[],int mk){ 33 for(int i=0;i<N;++i) tmp[i]=x[rvs[i]]; 34 for(int i=0;i<N;++i) x[i]=tmp[i]; 35 for(int i=2;i<=N;i<<=1){ 36 cp wn(cos(2*M_PI/i),mk*sin(2*M_PI/i)); 37 for(int k=0;k<N;k+=i){ 38 cp w(1,0); 39 for(int j=k;j<k+(i>>1);++j){ 40 _x=x[j],_y=x[j+(i>>1)]*w; 41 x[j]=_x+_y,x[j+(i>>1)]=_x-_y; 42 w=w*wn; 43 } 44 } 45 } 46 if(mk==-1) for(int i=0;i<N;++i) x[i].r/=N; 47 } 48 int main(){//freopen("ddd.in","r",stdin); 49 cin>>n>>m; 50 int x; 51 for(int i=0;i<n;++i){ 52 x=rd(); 53 a[n-1-i]=cp(x); 54 S+=x*x,s+=x; 55 } 56 for(int i=0;i<n;++i){ 57 x=rd(); 58 b[i]=b[i+n]=cp(x); 59 S+=x*x,s-=x; 60 } 61 s<<=1; 62 for(N=1,L=0;N<=(n<<1);N<<=1,++L); N<<=1,++L; 63 for(int i=0;i<N;++i){ 64 for(int j=i,k=0;j;j>>=1,++k) dg[k]=j&1; 65 for(int j=0;j<L;++j) rvs[i]=(rvs[i]<<1)|dg[j]; 66 } 67 /*for(int i=0;i<N;++i) cout<<(int)(a[i].r+0.5)<<" "; 68 cout<<endl; 69 for(int i=0;i<N;++i) cout<<(int)(b[i].r+0.5)<<" "; 70 cout<<endl;*/ 71 fft(a,1),fft(b,1); 72 for(int i=0;i<N;++i) c[i]=a[i]*b[i]; 73 fft(c,-1); 74 ll ans=inf; 75 for(int i=0;i<n;++i)for(int j=0;j<=m;++j){ 76 ans=min(ans,S+j*s+n*j*j-2*(ll)(c[n-1+i].r+0.5)); 77 ans=min(ans,S-j*s+n*j*j-2*(ll)(c[n-1+i].r+0.5)); 78 } 79 //for(int i=0;i<N;++i) cout<<(int)(c[i].r+0.5)<<" "; 80 cout<<ans<<endl; 81 return 0; 82 }