链接：https://www.luogu.com.cn/problem/P3723
题目描述：给定两个序列，每次可以旋转其中的一个或给其中一个加上一个数\(c\)，求两个序列对应位置的差的平方和所能达到的最小值。
题解：
\(\sum_{i=1}^{n}(x_{i}-y_{i}+c)^2\)
\(=\sum_{i=1}^{n}(x_{i}^2-2\times x_{i}\times y_{i}+y_{i}^2+c^2+c\times(x_{i}-y_{i}))\)
可以先求出\(c^2+c\times\sum_{i=1}^{n}(x_{i}-y_{i})\)的最小值， 这个可以利用二次函数顶点公式去求。
当然，还有旋转的操作，我们发现旋转操作只会影响\(2\times x_{i}\times y_{i}\)这一项，我们考虑求出顺时针旋转\(t\)次时\(2\times x_{i}\times y_{i}\)这一项的贡献。
我们可以得到旋转\(t\)次的答案为\(\sum_{i=1}^{n}2\times x_{i}\times y_{i+t}\)(当然,\(i+t>n\)时要化做\(i+t-n\))
令\(f_{i}=x_{n-i}\)，则答案可化作\(\sum_{i=1}^{n}2\times x_{n-i}\times y_{i+t}\)。
可以发现这是一个卷积的形式，跑\(fft\)即可。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct node
{
double x,y;
};
int n,m;
node tmp,w,wn,A[200001],B[200001],C[200001];
long long sum,res,X[200001],Y[200001],maxn;
const double Pi=asin(1)*2;
double c;
node make_node(double x,double y)
{
tmp.x=x;
tmp.y=y;
return tmp;
}
node operator + (node x,node y)
{
return make_node(x.x+y.x,x.y+y.y);
}
node operator - (node x,node y)
{
return make_node(x.x-y.x,x.y-y.y);
}
node operator * (node x,node y)
{
return make_node(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);
}
void FFT(int limit,node *a,int type)
{
if (limit==1)
return;
node a2[limit/2+1],b2[limit/2+1];
for (int i=0;i<limit;i+=2)
{
a2[i/2]=a[i];
b2[i/2]=a[i+1];
}
FFT(limit/2,a2,type);
FFT(limit/2,b2,type);
wn=make_node(1,0),w=make_node(cos(2*Pi/limit),type*sin(2*Pi/limit));
for (int i=0;i<limit/2;++i,wn=wn*w)
{
a[i]=a2[i]+b2[i]*wn;
a[i+limit/2]=a2[i]-b2[i]*wn;
}
return;
}
int main()
{
int limit=1;
cin>>n>>m;
for (int i=1;i<=n;++i)
cin>>X[i];
for (int i=1;i<=n;++i)
cin>>Y[i];
for (int i=1;i<=n;++i)
{
c+=(Y[i]-X[i])*1.0/n;
sum+=X[i]-Y[i];
res+=X[i]*X[i]+Y[i]*Y[i];
}
long long c1=floor(c),c2=ceil(c);
res+=min(c1*c1*n+2*c1*sum,c2*c2*n+2*c2*sum);
for (int i=0;i<=n;++i)
A[n-i].x=X[i];
for (int i=1;i<=n;++i)
B[i].x=Y[i];
while (limit<=2*n)
limit*=2;
FFT(limit,A,1);
FFT(limit,B,1);
for (int i=0;i<=limit;++i)
C[i]=A[i]*B[i];
FFT(limit,C,-1);
for (int i=0;i<=n-1;++i)
maxn=max(maxn,(long long)(C[i].x/limit+0.5)+(long long)(C[i+n].x/limit+0.5));
cout<<res-2*maxn<<endl;
return 0;
}