Description：
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。
但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。
在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号1,2,…,n，其中 n 为每个手环的装饰物个数， 第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手环的 i 号位置装饰物亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)：
$\sum_{i=1}^{n} (x_i-y_i)^2$
麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？
30%的数据满足n≤500, m≤10；
70%的数据满足n≤5000；
100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。
Input：
输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始亮度小于等于m。
接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。
Output：
输出一个数，表示两个手环能产生的最小差异值。注意在将手环改造之后，装饰物的亮度可以大于 m。
Analysis：
为了方便，我们称读入的n为rn，称FFT系数补全后的项数为n
首先拆项：
$(a-b-c)^2 = a^2+b^2-2ab+c^2+2c(b-a)$
可以发现除了$-2ab$这一项以外，其它的项都可以在$O(nm)$的时间算出来(似乎可以$O(n)$啊)
然后对于计算$\sum ab$，我们需要使用FFT加速：
那么相当于算：$\sum_{i=1}^{n} a_ib_i$， 很像卷积?把$b$数组倒一倒！
所以就是算：$\sum_{i=1}^{n} a_ib_{n-i}$ 即为卷积形式
然后就比较好做了，因为手环可旋转，枚举模rn的余数rol，然后把项数编号模rn为rol的都加起来，就是当前的$\sum ab$，过程非常巧妙，非常正确，可以自己举举例子。
Thoughts：
第一次写FFT，理解可能还比较生疏。。 数学很巧妙啊！
Code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<complex>
using namespace std;
#define LL long long
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define N (200000+5)
typedef complex<double> CMX;
const double PI = acos(-1.0);
CMX a[N], b[N], ab[N];
int rn, m, n, nbit, rev[N];
LL abint[N];
double vba, absqr;
inline void InitRever(){
nbit = 0; n = 1;
while(n < 2*rn+1) ++nbit, n <<= 1;
For(i, 1, n-1)
rev[i] = (rev[i>>1]>>1)|((i&1)<<(nbit-1));
}
void FFT(CMX *r, int dft){
For(i, 0, n-1) if(i < rev[i]) swap(r[i], r[rev[i]]);
CMX Wn, Wnk, x, y;
for(int step = 1; step < n; step <<= 1){
Wn = exp(CMX(0, dft*PI/step));
for(int j = 0; j < n; j += step<<1){
Wnk = CMX(1, 0);
For(i, j, j+step-1){
x = r[i], y = Wnk*r[i+step];
r[i] = x+y;
r[i+step] = x-y;
Wnk *= Wn;
}
}
}
if(dft == -1) For(i, 0, n-1) r[i] /= 1.0*n, abint[i] = (LL)(r[i].real()+0.5);
}
int main(){
scanf("%d%d", &rn, &m);
double tmp;
For(i, 0, rn-1) scanf("%lf", &tmp), a[i] = tmp,
vba += a[i].real(), absqr += a[i].real()*a[i].real();
Forr(i, rn-1, 0) scanf("%lf", &tmp), b[i] = tmp,
vba -= b[i].real(), absqr += b[i].real()*b[i].real();
InitRever();
FFT(a, 1); FFT(b, 1);
For(i, 0, n-1) ab[i] = a[i]*b[i];
FFT(ab, -1);
LL tans, ans = (1ll<<50);
For(rol, 0, rn-1){
tans = (1ll<<50);
For(c, 0, m)
tans = min(tans, c*c*rn+(LL)min(2*c*vba, -2*c*vba));
for(int i = rol; i < n; i += rn) tans -= 2*abint[i];
tans += (LL)absqr;
ans = min(ans, tans);
}
printf("%lld\n", ans);
return 0;
}