传送门
nttnttntt 入门题。
考虑展开要求的式子∑i=0n−1(xi−yi−c)2\sum_{i=0}^{n-1}(x_i-y_i-c)^2∑i=0n−1(xi−yi−c)2
=>∑i=0n−1(xi2+yi2+c2−2c(xi−yi)−2xiyi)\sum_{i=0}^{n-1}(x_i^2+y_i^2+c^2-2c(x_i-y_i)-2x_iy_i)∑i=0n−1(xi2+yi2+c2−2c(xi−yi)−2xiyi)
令sum=∑i=0n−1xi−yisum=\sum_{i=0}^{n-1}x_i-y_isum=∑i=0n−1xi−yi
=>(∑i=0n−1(xi2+yi2))+min{nc2−2sum∗c}−2∗max{∑i=0n−1xiyi}(\sum_{i=0}^{n-1}(x_i^2+y_i^2))+\min\{nc^2-2sum*c\}-2*\max\{ \sum_{i=0}^{n-1}x_iy_i\}(∑i=0n−1(xi2+yi2))+min{nc2−2sum∗c}−2∗max{∑i=0n−1xiyi}
化到这一步的时候我卡了一下。
考虑第一坨可以直接算，第二坨可以取二次函数对称轴附近求极值。
关键在于第三坨的极值。
这个怎么求呢？
考虑将bbb数组翻转。
这样对a,ba,ba,b进行nttnttntt，然后得到的新数列{zn}\{z_n\}{zn}中的zi+zn+iz_i+z_{n+i}zi+zn+i就对应着数列an,bna_n,b_nan,bn的一种对齐方法的和。
因此只需要在nttnttntt之后给zi+zn+iz_i+z_{n+i}zi+zn+i取个max\maxmax就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int mod=998244353,N=2e5+5;
int n,m,a[N],b[N],pos[N],ans=0,lim=1,tim=0,mx=0,sum=0;
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}
inline void ntt(int a[],int type){
for(int i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
int mult=(mod-1)>>1,typ=type==1?3:(mod+1)/3;
for(int wn,mid=1;mid<lim;mid<<=1,mult>>=1){
wn=ksm(typ,mult);
for(int len=mid<<1,j=0;j<lim;j+=len){
int w=1;
for(int k=0;k<mid;++k,w=(ll)w*wn%mod){
int a0=a[j+k],a1=(ll)a[j+k+mid]*w%mod;
a[j+k]=(a0+a1)%mod,a[j+k+mid]=(a0-a1+mod)%mod;
}
}
}
}
inline int calc(int x){return (n+1)*x*x-2*sum*x;}
int main(){
freopen("lx.in","r",stdin);
n=read()-1,m=read();
for(int i=0;i<=n;++i)a[i]=read(),ans+=a[i]*a[i],sum+=a[i];
for(int i=n;~i;--i)b[i]=read(),ans+=b[i]*b[i],sum-=b[i];
while(lim<=n*2)lim<<=1,++tim;
int p=sum/(n+1);
ans+=min(min(calc(p-1),calc(p)),calc(p+1));
for(int i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
ntt(a,1),ntt(b,1);
for(int i=0;i<lim;++i)a[i]=(ll)a[i]*b[i]%mod;
ntt(a,-1);
int inv=ksm(lim,mod-2);
for(int i=0;i<=n*2;++i)a[i]=(ll)a[i]*inv%mod;
for(int i=0;i<=n;++i)mx=max(mx,a[i]+a[i+n+1]);
cout<<ans-2*mx;
return 0;
}