「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;
}