CXK前来求助
查看原帖
CXK前来求助
160839
Prean楼主2020/5/31 17:30

输出53。。。我也是罪了。。。

求dalao帮忙看看QwQ

#include<cstdio>
#include<cmath>
typedef double db;
typedef long long ll;
const db Pi=acos(-1);
const int M=1<<17|5;
struct cpx{
	db x,y;
	cpx(db x=0,db y=0):x(x),y(y){}
	friend inline cpx operator+(cpx a,cpx b){
		return cpx(a.x+b.x,a.y+b.y);
	}
	friend inline cpx operator-(cpx a,cpx b){
		return cpx(a.x-b.x,a.y-b.y);
	}
	friend inline cpx operator*(cpx a,cpx b){
		return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
	}
}a[M],b[M];
int n,m,k,t[M];
ll x,y,ans(1e15),A[M],B[M];
void swap(cpx&a,cpx&b){
	cpx c=a;
	a=b;b=c;
}
void FFT(cpx*f,bool flag,int n){
	int k,i,p,len;cpx w,w1;
	for(i=0;i<n;++i)if(i<t[i])swap(f[i],f[t[i]]);
	for(p=2;p<=n;p<<=1){
		len=p>>1;w1=cpx(cos(2*Pi/p),sin((flag?1:-1)*2*Pi/p));
		for(k=0;k<n;k+=p){
			w=cpx(1);
			for(i=k;i<k+len;++i){
				cpx t=f[i+len]*w;
				f[i+len]=f[i]-t;f[i]=f[i]+t;
				w=w*w1;
			}
		}
	}
}
signed main(void){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i){
		scanf("%lld",A+i);
		x+=A[i]*A[i];y+=A[i];
	}
	for(i=1;i<=n;++i){
		scanf("%lld",B+i);
		x+=B[i]*B[i];y-=B[i];
	}
	for(i=1;i<=n;++i){
		a[i+n].x=a[i].x=A[i];
		b[i].x=B[n-i-1];
	}
	for(k=1;k<=(n*3);k<<=1);
	for(i=0;i<k;++i)t[i]=t[i>>1]>>1|(i&1?k>>1:0);
	FFT(a,1,k);FFT(b,1,k);
	for(i=0;i<=k;++i)a[i]=a[i]*b[i];
	FFT(a,-1,k);
	for(i=0;i<=k;++i)a[i].x=(ll)(a[i].x/k+0.5);
	for(i=1;i<=n;++i){
		for(j=-m;j<=m;++j){
			ll t=x+j*j*n+2ll*j*y-2ll*(ll)a[i+n].x;
			if(t<ans)ans=t;
		}
	}
	printf("%lld",ans);
}

2020/5/31 17:30
加载中...