「AH2017/HNOI2017」礼物 - FFT

题目链接:传送门

Description

有两个长度为nn的序列,序列元素为[1,m][1,m] ,定义两个序列的差异值为ni=(xiyi)2n_i=\sum(x_i-y_i)^2

可以给第一个序列加上一个长度c,第二个序列可以任意旋转,问最小差异值。

Constraints

n50000,m100n\le50000,m\le100

Solution

假设差异值最小的序列为A和B,则其差异值为

(aibi+c)\sum (a_i-b_i+c) =(ai2+bi2)+nc2+2c(aibi)22aibi=\sum (a_i^2 + b_i^2) + nc^2 + 2c\sum(a_i-b_i)^2-2\sum a_i b_i

第一项已知,二三项可以通过枚举c求出最小值,因此我们只需要aibi\sum a_i b_i最大

将A翻转之后原式变为ani+1bi\sum a_{n-i+1} b_i 显然它是一个卷积的形式。

我们将翻转后的A序列倍长,卷上B,用FFT即可(答案即为卷积后n+1项至2n项中间的最大值,这个自己推一推就能发现)

PS: FFT注意最后要四舍五入。。。

Code

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 1000000 + 100;
const double PI = acos(-1.0);

struct Complex
{
double x, y;
Complex() {x = 0, y = 0;}
friend Complex operator + (const Complex &a, const Complex &b)
{
Complex c;
c.x = a.x + b.x, c.y = a.y + b.y;
return c;
}
friend Complex operator - (const Complex &a, const Complex &b)
{
Complex c;
c.x = a.x - b.x, c.y = a.y - b.y;
return c;
}
friend Complex operator * (const Complex &a, const Complex &b)
{
Complex c;
c.x = a.x * b.x - a.y * b.y;
c.y = a.x * b.y + a.y * b.x;
return c;
}
};

Complex F1[Maxn], F2[Maxn];

int A[Maxn], B[Maxn];
int N, M, limit, NN;
int rev[Maxn];

inline void FFT_init()
{
for (int i = 1; i <= N * 2; ++i) F1[i].x = (double)A[i], F2[i].x = (double)B[i];
M = N * 3;
for (NN = 1; NN <= M; NN <<= 1) limit ++;
for (int i = 0; i < NN; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (1 << (limit - 1)));
}

inline void FFT (Complex *A, int type)
{
for (int i = 0; i <= NN; ++i) if (i < rev[i]) swap(A[i], A[rev[i]]);
for (int mid = 1; mid < NN; (mid <<= 1))
{
Complex Wn;
Wn.x = cos(PI / mid), Wn.y = type * sin(PI / mid);
for (int I = (mid << 1), i = 0; i < NN; i += I)
{
Complex W;
W.x = 1;
for (int j = 1; j <= mid; ++j, W = W * Wn)
{
Complex x = A[i + j - 1], y = W * A[i + j + mid - 1];
A[i + j - 1] = x + y, A[i + j + mid - 1] = x - y;
}
}
}
if (type == -1) for (int i = 0; i <= NN; ++i) A[i].x /= NN;
}

main()
{
#ifdef hk_cnyali
freopen("gift.in", "r", stdin);
freopen("gift.out", "w", stdout);
#endif
scanf("%lld%lld", &N, &M);
int sum1 = 0, sum2 = 0, ans = 0;
for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]), sum1 += A[i] * A[i], sum2 += A[i];
for (int i = 1; i <= N; ++i) scanf("%lld", &B[i]), sum1 += B[i] * B[i], sum2 -= B[i];

ans = LLONG_MAX;
for (int c = M - 100; c <= M + 100; ++c)
ans = min(ans, N * c * c + 2 * c * sum2);
ans += sum1;
reverse(A + 1, A + N + 1);
for (int i = 1; i <= N; ++i) A[i + N] = A[i];

FFT_init();
FFT(F1, 1), FFT(F2, 1);
for (int i = 0; i <= NN; ++i) F1[i] = F1[i] * F2[i];
FFT(F1, -1);

sum1 = 0ll;
for (int i = N + 1; i <= 2 * N; ++i) sum1 = max(sum1, (int)(F1[i].x + 0.5));

printf("%lld\n", ans - 2ll * sum1);
return 0;
}
感谢你的赞赏!