题目链接：传送门

Description

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

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

Constraints

n≤50000,m≤100n\le50000,m\le100

Solution

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

∑(ai−bi+c)\sum (a_i-b_i+c) =∑(ai2+bi2)+nc2+2c∑(ai−bi)2−2∑aibi=\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翻转之后原式变为∑an−i+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;
}