题目相关

题目链接: 洛谷 P3723 [AH2017/HNOI2017] 礼物

题目描述

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

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

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1 \sim n$，其中 $n$ 为每个手环的装饰物个数， 第 $1$ 个手环的 $i$ 号位置装饰物亮度为 $x_i$，第 $2$ 个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为（参见输入输出样例和样例解释）：

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
5 6
1 2 3 4 5
6 3 3 4 5

输出 #1

1
1

说明/提示

【样例解释】

需要将第一个手环的亮度增加 $1$，第一个手环的亮度变为：$2,3,4,5,6$

旋转一下第二个手环。对于该样例，是将第二个手环的亮度 $6,3,3,4,5$ 向左循环移动一个位置，使得第二手环的最终的亮度为：$3,3,4,5,6$。

此时两个手环的亮度差异值为 $1$。

【数据范围】

对于 $30%$ 的数据，$n \le 500$，$m \le 10$；

对于 $70%$ 的数据，$n \le 5000$；

对于 $100%$ 的数据，$1 \le n \le 50000$, $1 \le a_i \le m \le 100$。

题目解析

对于调整亮度，既可以对第一个手环调整，也可以给第二个手环调整，其实也就是对整体 $a_i-b_i$ 加上/减去了任意值，不妨设为 $c$。那么公式修正为：

$$\sum_{i=1}^{n}(x_i-y_i+c)^2$$

首先拆解一下式子，找一下其中的变量：

$$
\begin{aligned}
& \sum_{i=1}^{n}(x_i-y_i+c)^2 \\
=& \sum_{i=1}^{n}((x_i-y_i)+c)^2 \\
=& \sum_{i=1}^{n}((x_i-y_i)^2 + 2c(x_i-y_i) + c^2) \\
=& \sum_{i=1}^{n}(x_i^2 - 2x_iy_i + y_i^2) + 2c\sum_{i=1}^{n}(x_i-y_i) + nc^2 \\
=& \sum_{i=1}^{n}(x_i^2 + y_i^2) - 2\sum_{i=1}^{n}x_iy_i + 2c\sum_{i=1}^{n}(x_i-y_i) + nc^2 \\
=& nc^2 + \sum_{i=1}^{n}(x_i^2 + y_i^2) + 2c\sum_{i=1}^{n}(x_i-y_i) - 2\sum_{i=1}^{n}x_iy_i
\end{aligned}
$$

前半部分是关于 $c$ 的二次函数，直接可求得极值。关键在于 $\sum_{i=1}^{n}x_iy_i$ 的值，其越大，最终值越小。这是一个经典的卷积形式：不妨设 $x^{r}$ 是 $x$ 翻转后的序列，那么：
$$\sum_{i=1}^{n} x_iy_i = \sum_{i=1}^{n} x^r_{n-i+1}y_i = x^r * y$$

考虑到翻转，可以将 $x^r$ 复制一份放在后面，$y$ 在后面拼接 $0$，那么最后卷积得到的第 $n+1$ 到 $2n$ 项即是每个翻转得到的值。

最终计算两部分极值，即可获得答案。

代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
#define ll long long
const int maxn = 131072 << 1;

namespace NTT {
    const ll mod = 998244353;
    const ll G = 3;
    const ll Gi = 332748118;
    ll a[maxn], b[maxn], c[maxn << 1];
    int limit, limitBit, r[maxn << 1];
    ll inv;

    ll quickPow(ll x, ll k) {
        ll res = 1;
        while (k) {
            if (k & 1)
                res = res * x % mod;
            x = x * x % mod;
            k >>= 1;
        }
        return res;
    }

    void init(int len) {
        limit = 1;
        while (limit <= (len * 2)) {
            limit <<= 1;
            limitBit++;
        }
        for (int i = 0; i < limit; i++)
            r[i] = (i & 1) * (limit >> 1) + (r[i >> 1] >> 1);
        inv = quickPow(limit, mod - 2);
    }

    void NTT(ll *A, bool isInverse) {
        for (int i = 0; i < limit; i++)
            if (i < r[i])
                swap(A[i], A[r[i]]);

        for (int k = 1; k < limit; k <<= 1) {
            ll unit = quickPow(isInverse ? Gi : G, (mod - 1) / (k << 1));
            for (int i = 0; i < limit; i += (k << 1)) {
                for (ll j = i, g = 1; j < i + k; ++j, g = g * unit % mod) {
                    ll x = A[j], y = g * A[j + k] % mod;
                    A[j] = (x + y) % mod;
                    A[j + k] = (x - y + mod) % mod;
                }
            }
        }

        if (isInverse) {
            for (int i = 0; i < limit; ++i) {
                A[i] = A[i] * inv % mod;
            }
        }
    }

    void work() {
        NTT(a, false);
        NTT(b, false);
        for (int i = 0; i < limit; ++i) {
            c[i] = a[i] * b[i] % mod;
        }
        NTT(c, true);
    }
}

int n, m;
int a[maxn], b[maxn];
ll sumx2, sumy2, sumx, sumy;

ll calcC(ll A, ll B, ll C) {
    double x = -1.0 * (B) / (2 * A);
    ll xMin = floor(x), xMax = ceil(x);
    ll resMin = A * xMin * xMin + B * xMin + C;
    ll resMax = A * xMax * xMax + B * xMax + C;
    return min(resMin, resMax);
}

ll calcXY() {
    NTT::init(2 * n);
    for (int i = 0; i < n; ++i) {
        NTT::a[i] = NTT::a[i + n] = a[i];
        NTT::b[i] = b[n - i - 1];
    }

    NTT::work();
    ll res = 0;
    for (int i = n - 1; i < 2 * n; ++i) {
        res = max(res, NTT::c[i]);
    }
    return res;
}   

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
        sumx += a[i];
        sumx2 += a[i] * a[i];
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d", &b[i]);
        sumy += b[i];
        sumy2 += b[i] * b[i];
    }

    ll ans = sumx2 + sumy2 + calcC(1ll * n, 2 * (sumx - sumy), 0) - 2 * calcXY();
    printf("%lld\n", ans);

    return 0;
}