AHOI/HNOI2017礼物

(sum)加乘法( o)卷积！！

期望时间复杂度(O(nlog_n))

写公式一定要简洁明了，凸出重点，不然自己都看不懂

SOL:

(ans=sum (a_i-b_i+c)^2=sum a_i^2+sum b_i^2+nc^2+2(sum a_i-b_i)c-sum a_ib_i)

只有(sum a_ib_i)无法(O(n))求，发现可用减法卷积完成

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=5e4+4;
const double pi=acos(-1.0);
struct complx{
	double x,y;
	complx(double xx=0,double yy=0){x=xx;y=yy;}
	inline complx operator -(const complx &a)const{
		return complx(x-a.x,y-a.y);
	}
	inline complx operator +(const complx &a)const{
		return complx(x+a.x,y+a.y);
	}
	inline complx operator *(const complx &a)const{
		return complx(x*a.x-y*a.y,x*a.y+y*a.x);
	}
}a[N<<4],b[N<<4];
int n,m,c,ts,ans,len,lim,rev[N<<4];
inline void FFT(complx *A,int len,int lim,int fl){
	for(int i=0;i<len;i++){
		rev[i]=(rev[i>>1]>>1)|((i&1)<<lim-1);
		if(i<rev[i])swap(A[i],A[rev[i]]);
	}
	for(int mid=1;mid<len;mid<<=1){
		complx wn(cos(pi/mid),fl*sin(pi/mid));
		for(int i=0;i<len;i+=mid<<1){
			complx w(1,0);
			for(int j=0;j<mid;j++,w=w*wn){
				complx u=A[i+j],v=w*A[i+j+mid];
				A[i+j]=u+v;A[i+j+mid]=u-v;
			}
		}
	}
}
signed main(){
	n=read();m=read();
	for(int i=1,x;i<=n;i++){
		a[i].x=a[i+n].x=x=read();
		ans+=x*x;
		ts-=x;
	} 
	for(int i=1,x;i<=n;i++){
		b[n-i+1].x=x=read();
		ans+=x*x;
		ts+=x;
	}
	c=floor((double)ts/n+0.5);
	ans+=n*c*c-2*c*ts;
	len=1;lim=0;
	while(len<3*n+2){len<<=1;lim++;}
	FFT(a,len,lim,1);FFT(b,len,lim,1);
	for(int i=0;i<len;i++)a[i]=a[i]*b[i];
	FFT(a,len,lim,-1);
	ts=0;
	for(int i=n+1;i<=(n<<1);i++)ts=max(ts,(int)floor(a[i].x/len+0.5));
	cout<<ans-(ts<<1)<<"
";
	return (0-0);
}