【BZOJ 4827】[HNOI2017] 礼物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4827
神犇题解:https://blog.sengxian.com/solutions/hnoi-2017-day1

解题报告

这题怎么讲呢?如果你不知道循环卷积,那么你只有$70$分
比如说:我 _(:з」∠)_

百度百科上循环卷积这个词条的例题就是这题
所以知道循环卷积的定义,然后写一个$FFT$就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define CPL complex<double>
using namespace std;

const int N = 200000;
const int INF = 2e9;
const double EPS = 0.5;
const double PI = acos(-1);

int n,m,B,C,mx,len,tt,f[N],pos[N];
CPL a[N],b[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline void FFT(CPL *arr, int ty) {
	for (int i=0;i<len;i++) {
		if (pos[i] < i) {
			swap(arr[pos[i]], arr[i]);
		}
	}
	for (int ll=1;ll<len;ll<<=1) {
		CPL wn(cos(PI/ll), sin(PI/ll)*ty);
		for (int i=0;i<len;i+=ll*2) {
			CPL w(1,0);
			for (int j=0;j<ll;j++,w=w*wn) {
				CPL tmp = arr[i+j+ll] * w;
				arr[i+j+ll] = arr[i+j] - tmp;
				arr[i+j] = arr[i+j] + tmp;
			}
		}
	}
	if (ty == -1) {
		for (int i=0;i<len;i++) {
			arr[i] /= len;
		}
	}
}

int main() {
	n = read(); m = read();
	for (int i=0,tmp;i<n;i++) {
		B += (tmp = read()) << 1;
		C += tmp * tmp;
		a[i] = CPL{tmp, 0};
	}
	for (int i=0,tmp;i<n;i++) {
		B -= (tmp = read()) << 1;
		C += tmp * tmp;
		b[n-i] = CPL{tmp, 0};
	}
	
	for (len=1,tt=-1;len<n*2;len<<=1,++tt);
	for (int i=1;i<len;i++) {
		pos[i] = pos[i>>1]>>1;
		if (i&1) {
			pos[i] |= 1 << tt;
		}
	}
	FFT(a, 1);
	FFT(b, 1);
	for (int i=0;i<len;i++) {
		a[i] = a[i] * b[i];
	}
	FFT(a, -1);
	for (int i=n;i<len;i++) {
		a[i%n] += a[i];
	}
	for (int i=0;i<n;i++) {
		f[i] = a[i].real() + EPS;
		mx = max(f[i], mx);
	}
	C = C - 2 * mx;
	int p1 = -1.0 * B / 2 / n + EPS;
	int p2 = -1.0 * B / 2 / n - EPS;
	printf("%d\n",min(p1*p1*n+B*p1, p2*p2*n+B*p2) + C);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注