关键词:快速傅里叶变换FFT 相关题目:[HNOI2017]礼物

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 nn 个装饰物,并且每个装饰物都有一定的亮度。

但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的自然数 cc(即非负整数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 ,其中 nn 为每个手环的装饰物个数, 第 11 个手环的 ii 号位置装饰物亮度为 xix_i,第 22 个手环的 ii 号位置装饰物亮度为 yiy_i,两个手环之间的差异值为(参见输入输出样例和样例解释):

i=1n(xiyi)2\sum_{i=1}^{n} (x_i-y_i)^2

麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?

Input&Output

Input: 输入数据的第一行有两个数 n,mn, m,代表每条手环的装饰物的数量为nn,每个装饰物的初始亮度小于等于mm

接下来两行,每行各有 nn 个数,分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

输出格式: 输出一个数,表示两个手环能产生的最小差异值。注意在将手环改造之后,装饰物的亮度可以大于 mm

Solution

\begin{align} Ans & = \sum_{i=1}^{n} (x_i-yi+c)^2 \ & = \sum{i=1}^{n} x^2 +\sum{i=1}^{n} y^2 - 2\sum{i=1}^{n}x_i~yi + nc^2 + 2(~ \sum{i=1}^n xi - \sum{i=1}^{n}y_i ~)c \end{align}

注意到关于 cc 的是一个二次函数,故只需确定 的最大值即可。

考虑反转 xx ,因为构成手环的为一个环,我们假设 xx 的第一位对应 yy 的第 kk 位。并约定 yn+i=yiy_{n+i} = y_{i} 。于是:

这时,我们倍长 yy ,考虑 xxyy 的卷积即可。

AC代码

4827

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
#include <cstdio>
#include <cmath>
#include <memory>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
const double pi = acos(-1);
const int N = 262144+2;

struct cpx {
double r, i;
cpx(){}
cpx(double _r, double _i) {r=_r, i=_i;}
inline cpx operator +(const cpx &rhs)const{
return cpx(r+rhs.r, i+rhs.i);
}
inline cpx operator -(const cpx &rhs)const{
return cpx(r-rhs.r, i-rhs.i);
}
inline cpx operator *(const cpx &rhs)const{
return cpx(r*rhs.r - i*rhs.i, r*rhs.i + i*rhs.r);
}
inline void operator *=(const cpx &rhs) {
*this = *this * rhs;
}
} a[N], b[N];

int n, m, x, sumx, sumy;
int ans = 0;
int R[N];

inline void FFT(int n, cpx *a, int f) {
rep(i,0,n-1)
if(R[i] > i) std::swap(a[R[i]], a[i]);

for(re l = 1; l < n; l <<= 1) {
cpx wn(cos(pi/l), f*sin(pi/l));
for(re j = 0; j < n; j += (l<<1)) {
cpx omega(1.0, 0.0);
for(re k = 0; k < l; ++k, omega*=wn) {
cpx t = omega * a[j+k+l];
a[j+k+l] = a[j+k] - t;
a[j+k] = a[j+k] + t;
}
}
}

if(f==-1)
rep(i,0,n-1) a[i].r /= n;
}

int main() {
scanf("%d%d", &n, &m);
drep(i,n-1,0)
scanf("%d", &x), sumx += x, ans += x*x, a[i] = cpx(1.0*x, 0.0);
rep(i,0,n-1)
scanf("%d", &x), sumy += x, ans += x*x, b[i] = cpx(1.0*x, 0.0);
rep(i,0,n-1) b[i+n] = b[i];
int _n = 1;
while(_n <= 3*n-3) _n <<= 1;
rep(i,0,_n-1)
R[i]=( (R[i>>1]>>1) | (_n>>(i&1)) ) & (_n-1);

FFT(_n, a, 1), FFT(_n, b, 1);
rep(i,0,_n-1) a[i] *= b[i];
FFT(_n, a, -1);

double maxx=0;
rep(i,n-1,n*2-1) maxx = max(maxx, a[i].r);
ans -= (int)round(maxx*2);

int c = (int)round( -(double)(sumx-sumy)/(double)n);
ans += n*c*c + 2*(sumx-sumy)*c;
printf("%d\n", ans);
}