思路
对题目给出的式子化简一下
设第二个手环增加了c
[egin{align}&sum_{i=1}^n (x_i-(y_i+c))^2\=&sum_{i=1}^n x_i-2x_i(y_i+c)+(y_i+c)^2\=&sum_{i=1}^n x_i^2 - 2x_iy_i-2x_ic+y_i^2+2y_ic+c^2\=&sum_{i=1}^n x_i^2 - sum_{i=1}^n2x_iy_i-sum_{i=1}^n2x_ic+sum_{i=1}^ny_i^2+sum_{i=1}^n2y_ic+sum_{i=1}^nc^2end{align}
]
所以只需要最大化(sum_{i=1}^n x_iy_i)即可
然后设(f(x))和(g(x))，(f(x))的第i项系数是(x_i)，(g(x))的第i项系数是(y_i)，所以(f(x)*g(x))的第n+1项系数就是第一个环的第n个和第二个环的第1个重合的结果，然后以此类推，断环为链，所以倍长f，把g反转之后卷积，n+1~2n项的最大值即为所求，剩下的可以二次函数极值或者暴力枚举c
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MAXN = 300000;
const int MOD = 998244353;
const int G = 3;
const int invG = 332748118;
struct Poly{
int t,data[MAXN];
Poly(){};
};
int pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(1LL*a*ans)%MOD;
a=(1LL*a*a)%MOD;
b>>=1;
}
return ans;
}
void output(Poly a){
putchar('
');
printf("a.times=%lld
",a.t);
putchar('
');
for(int i=0;i<=a.t;i++)
printf("%lld ",a.data[i]);
putchar('
');
putchar('
');
}
void rev(Poly &a){
for(int i=0,j=a.t;i<j;i++,j--)
swap(a.data[i],a.data[j]);
}
void save(Poly &a,int top){
for(int i=top+1;i<=a.t;i++)
a.data[i]=0;
a.t=top;
}
void NTT(Poly &a,int n,int opt){
int lim=0;
while((1<<lim)<n)
lim++;
n=(1<<lim);
for(int i=0;i<n;i++){
int t=0;
for(int j=0;j<lim;j++)
if((i>>j)&1)
t|=(1<<(lim-j-1));
if(i<t)
swap(a.data[i],a.data[t]);
}
for(int i=2;i<=n;i<<=1){
int len=i/2;
int tmp=pow((opt)?G:invG,(MOD-1)/i);
for(int j=0;j<n;j+=i){
int arr=1;
for(int k=j;k<j+len;k++){
int t=(1LL*arr*a.data[k+len])%MOD;
a.data[k+len]=(a.data[k]-t+MOD)%MOD;
a.data[k]=(a.data[k]+t+MOD)%MOD;
arr=(1LL*arr*tmp)%MOD;
}
}
}
if(!opt){
int invN = pow(n,MOD-2);
for(int i=0;i<n;i++)
a.data[i]=(a.data[i]*invN)%MOD;
}
}
void mul(Poly &a,Poly b){//a=a*b
int num=a.t+b.t,lim=0;
while((1<<lim)<=(num+2))
lim++;
lim=(1<<lim);
NTT(a,lim,1);
NTT(b,lim,1);
for(int i=0;i<lim;i++)
a.data[i]=(1LL*a.data[i]*b.data[i])%MOD;
NTT(a,lim,0);
for(int i=num+1;i<lim;i++)
a.data[i]=0;
a.t=num;
}
int n,m,x[MAXN],y[MAXN];
Poly a,b;
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&x[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&y[i]);
}
for(int i=0;i<n;i++)
a.data[i]=x[i+1];
for(int i=0;i<n;i++)
a.data[i+n]=x[i+1];
a.t=2*n-1;
for(int i=0;i<n;i++)
b.data[i]=y[i+1];
b.t=n-1;
rev(a);
mul(a,b);
int ans=0;
// output(a);
for(int i=n;i<=2*n-1;i++)
ans=max(a.data[i],ans);
// printf("%lld
",ans);
int sum1=0,sum2=0;
for(int i=1;i<=n;i++)
sum1+=y[i]-x[i],sum2+=x[i]*x[i]+y[i]*y[i];
int last=0x3f3f3f3f3f3f3f3fLL;
// printf("%lld %lld
",sum1,sum2);
for(int c=-m;c<=m;c++)
last=min(last,abs(n*c*c+2*c*sum1+sum2-2*ans));
printf("%lld
",last);
return 0;
}