Description
Solution
设y[i+k]=y[i]+n。
由于我们要最优解，则假如将x[i]和y[σ[i]]连线的话，线是一定不会交叉的。
所以，$ans=\sum (x_{i}-y_{i+s}+c)^{2}$
拆开得$ans=\sum (x_{i}^{2}+y_{i+s}^{2}+c^{2}-2x_{i}y_{i+s}+2x_{i}c-2y_{i+s}c)$
其中，$x_{i}y_{i+s}$是卷积形式。
我们把经过处理的y数组reverse一下，和x数组进行卷积(这里用ntt似乎会爆常数，fft大法好)。然后针对不同的s，得到以c为未知数的所有常数或系数，ans就是一个二次函数了。c用公式解就可以。
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const double pi=acos(-1); struct C { double r,i; friend C operator+(C a,C b){return C{a.r+b.r,a.i+b.i};} friend C operator*(C a,C b){return C{a.r*b.r-a.i*b.i,a.i*b.r+a.r*b.i};} friend C operator-(C a,C b){return C{a.r-b.r,a.i-b.i};} }fx[100010],fy[100010]; int rev[100010]; void fft(C *num,int n,int dft) { for (int i=1;i<n;i++) if (i<rev[i]) swap(num[i],num[rev[i]]); for (int step=1;step<n;step<<=1) { C wn{cos(pi/step),sin(pi/step)*dft}; for (int j=0;j<n;j+=step*2)//从0开始！ { C w{1,0}; for (int k=0;k<step;k++,w=w*wn) { C x=num[j+k],y=w*num[j+k+step]; num[j+k]=x+y; num[j+k+step]=x-y; } } } if (dft==-1) for (int i=0;i<n;i++) num[i].r/=n; } int T,n,k,len,L; int x[4010],y[8010]; ll sumx[8010],sumy[8010],sumx2[8010],sumy2[8010]; int main() { scanf("%d",&T); while (T--) { scanf("%d%d",&n,&k); memset(sumx,0,sizeof(sumx)); memset(sumy,0,sizeof(sumy)); memset(sumx2,0,sizeof(sumx2)); memset(sumy2,0,sizeof(sumy2)); memset(fx,0,sizeof(fx));memset(fy,0,sizeof(fy)); for (int i=1;i<=k;i++) { scanf("%d",&x[i]); sumx[i]=sumx[i-1]+x[i],sumx2[i]=sumx2[i-1]+1ll*x[i]*x[i]; } for (int i=1;i<=k;i++) {scanf("%d",&y[i]);y[k+i]=y[i]+n;} for (int i=1;i<=2*k;i++) sumy[i]=sumy[i-1]+y[i],sumy2[i]=sumy2[i-1]+1ll*y[i]*y[i]; for (int i=1;i<=k;i++) fx[i-1].r=x[i]; for (int i=0,j=2*k;j;i++,j--) fy[i].r=y[j]; len=1,L=0; for (;len<2*k;len<<=1,L++); L++;len<<=1; for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|(i&1)<<(L-1); fft(fx,len,1);fft(fy,len,1); for (int i=0;i<len;i++) fx[i]=fx[i]*fy[i]; fft(fx,len,-1); ll re,c,b,ans=1e13; for (int i=2*k-1,j=0;i>=k;i--,j++) { re=fx[i].r+0.2; re=-2*re+sumx2[k]+sumy2[j+k]-sumy2[j]; b=2*(sumx[k]-sumy[j+k]+sumy[j]); c=-b/(2*k); ans=min(ans,k*c*c+c*b+re); c++; ans=min(ans,k*c*c+c*b+re); } cout<<ans<<endl; } }