标签：node 200001 return int AHOI2017 sum times HNOI2017 礼物
链接：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
#include
#include
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="" }="" fft(limit="" 2,a2,type);="" 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="" return;="" int="" main()="" 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<
标签：node,
200001,
return,
int,
AHOI2017,
sum,
times,
HNOI2017,
礼物
From： https://www.cnblogs.com/zhouhuanyi/p/16983528.html