题解

二项式展开，然后暴力FFT就好了。会发现有一个卷积与c无关，我们找一个最小的项就行了。

Tips:记得要倍长其中一个数组，防止FFT出锅

代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 5e4+10;

const double pi = acos(-1.0);

struct Complex{

	double r,i;

	Complex(double r,double i):r(r),i(i){}

	Complex(){}

} A[maxn<<4],B[maxn<<4];

Complex operator + (Complex a,Complex b) {

	return Complex(a.r+b.r,a.i+b.i);

}

Complex operator - (Complex a,Complex b) {

	return Complex(a.r-b.r,a.i-b.i);

}

Complex operator * (Complex a,Complex b) {

	return Complex(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);

}

void operator *= (Complex &a,Complex b) {

	a=a*b;

}

void fft(Complex *a,int n,int inv) {

	for(int i = 1,j=n>>1;i<n-1;++i) {

		if(i<j) swap(a[i],a[j]);

		int k = n>>1;

		while(j>=k) j-=k,k>>=1;

		j+=k;

	}

	for(int j = 2;j<=n;j<<=1) {

		Complex wn(cos(2*pi/j*inv),sin(2*pi/j*inv));

		for(int i = 0;i<n;i+=j) {

			Complex w(1,0);

			for(int k = i;k<i+(j>>1);++k) {

				Complex u(a[k]),t(a[k+(j>>1)]*w);

				a[k]=u+t;

				a[k+(j>>1)]=u-t;

				w*=wn;

			}

		}

	}

	if(inv == -1)

		for(int i = 0;i<n;++i) a[i].r/=n;

}

int n,m;

int a[maxn],b[maxn];

ll aa,bb,sa,sb;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	cin>>n>>m;

	for(int i = 0;i<n;++i) cin>>a[i];

	for(int i = 0;i<n;++i) cin>>b[i];

	for(int i = 0;i<n;++i) {

		aa+=a[i]*a[i];

		bb+=b[i]*b[i];

		sa+=a[i];

		sb+=b[i];

	}

	for(int i = 0;i<n;++i) A[n-i].r=a[i],B[i].r=B[i+n].r=b[i];

	int lmt = 1;

	while(lmt<=2*n) lmt<<=1;

	fft(A,lmt,1);fft(B,lmt,1);

	for(int i = 0;i<lmt;++i) A[i]*=B[i];

	fft(A,lmt,-1);

	ll mn = 0;

	for(int i = 0;i<2*n;++i) {

		mn = max(mn , (ll)(A[i].r+0.5));

	}

	ll ans = 10000000000000000LL;

	for(int c = -m;c<=m;++c) {

		ll cc = 1LL*n*c*c;

		ans = min(ans , aa+bb+cc+2LL*sa*c-2LL*sb*c-2LL*mn);

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

【文文殿下】[AH2017/HNOI2017]礼物

题解

二项式展开，然后暴力FFT就好了。会发现有一个卷积与c无关，我们找一个最小的项就行了。

Tips:记得要倍长其中一个数组，防止FFT出锅

代码如下：

最新文章

热门文章