「AH2017/HNOI2017」礼物

发表于 | 分类于 | | 浏览量： 次

一个经典套路。

传送门

洛谷P3723

BZOJ4827

题解

首先来看下题目里的式子：

其中$\sum x_i^2+y_i^2$为定值，$\sum c^2+2cx_i-2cy_i-2x_iy_i$在确定了$c$的值之后也是定值，并且c的值非常小可以暴枚，所以只需要考虑$\sum x_iy_i$。

由于是一个环，按照套路，可以先将$x_i$复制一遍。

设$C_i$为旋转了$i$个单位后$\sum x_iy_i$的值，有：

这个式子不是很好看，于是我们把$y$（$x$也行）倒过来，那么就有：

然后不难发现，$x$与$y$下标之和为$n+i+1$的数将被乘起来然后对$C_i$造成贡献，所此时以$C_i$就等于多项式$x_1\cdot x+x_2\cdot x^2+\cdots x_n\cdot x^n$与$y_1\cdot x+y_2\cdot x^2+\cdots y_n\cdot x^n$卷积卷起来之后$x^{i+n+1}$项的系数。

然后NTT求个卷积然后取个最小值就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=50005,TT=998244353;
int n,m,r[maxn<<3],X[maxn],Y[maxn],A[maxn<<3],B[maxn<<3],C[maxn<<3],ans=2e9;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void NTT(int* A,int limit,int typ)
{
	for(int i=0;i<limit;i++)
		if(i<r[i])
			swap(A[i],A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1)
	{
		int gn=QP(3,(TT-1)/(mid<<1));
		if(typ<0) gn=QP(gn,TT-2);
		for(int j=0;j<limit;j+=mid<<1)
		{
			int g=1;
			for(int k=0;k<mid;k++,g=(LL)g*gn%TT)
			{
				int x=A[j+k],y=(LL)g*A[j+k+mid]%TT;
				A[j+k]=(x+y)%TT;
				A[j+k+mid]=(x-y+TT)%TT;
			}
		}
	}
	if(typ<0)
	{
		int inv=QP(limit,TT-2);
		for(int i=0;i<limit;i++) A[i]=(LL)A[i]*inv%TT;
	}
}
inline int Calc(int c){int ret=0;for(int i=1;i<=n;i++)ret+=X[i]*X[i]+Y[i]*Y[i]+c*c+2*X[i]*c-2*Y[i]*c;return ret;}
inline void Solve()
{
	for(int i=1;i<=n;i++) A[i]=A[i+n]=X[i];
	for(int i=1;i<=n;i++) B[i]=Y[i];
	reverse(A+1,A+1+n*2);
	int limit=1,l=0;
	while(limit<=n+n+m){limit<<=1;l++;}
	for(int i=0;i<limit;i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	NTT(A,limit,1);
	NTT(B,limit,1);
	for(int i=0;i<limit;i++) C[i]=(LL)A[i]*B[i]%TT;
	NTT(C,limit,-1);
	for(int c=-m;c<=m;c++)
		if(Calc(c)<ans)
			ans=Calc(c);
	int tep=0;
	for(int i=1;i<=n;i++)
		if(C[n+i]>tep)
			tep=C[n+i];
	ans-=2*tep;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) X[i]=read();
	for(int i=1;i<=n;i++) Y[i]=read();
	Solve();
	printf("%d\n",ans);
	return 0;
}