[HNOI 2017]礼物

时间：2023-03-09 05:45:47
[HNOI 2017]礼物

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手 环的 i 号位置装饰物亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： $$\sum_{i=1}^{n}(x_i-y_i)^2$$ 麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？

Input

输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始亮度小于等于m。
接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

Output

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

Sample Input

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

Sample Output

1

HINT

【样例解释】
需要将第一个手环的亮度增加1，第一个手环的亮度变为： 2 3 4 5 6 旋转一下第二个手环。对于该样例，是将第二个手环的亮度6 3 3 4 5向左循环移动一个位置，使得第二手环的最终的亮度为：3 3 4 5 6。 此时两个手环的亮度差异值为1。

【数据范围】

30%的数据满足n≤500, m≤10；

70%的数据满足n≤5000；

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

题解

我们假设第二个手环偏移量为 $p$ ，第二个手环增加的亮度为 $c$ 。由于两个手环亮度均可修改，如果第一个手环增加亮度为 $c$ 就相当于第二个手环减小的亮度为 $c$ 。一个容易得到的结论就是： $|c|\leq m$ 。在此基础上，我们要求的就是 $$\min_{\begin{aligned}0\leq p<n~~\\-m\leq c\leq m\end{aligned}}\sum_{i=0}^{n-1}(x_i-y_{(i+p)mod~n}-c)^2$$

将求和式拆开，我们得到 $$\sum_{i=0}^{n-1}(x_i^2+y_i^2+c^2+2y_ic-2x_ic)-2\sum_{i=0}^{n-1}x_iy_{(i+p)mod~n}$$

注意到前面那个求和式与偏移量 $p$ 是没有关系的，后面的求和式是和亮度增量 $c$ 是没有关系的。我们可以求出前式的最小值，与后式的最大值，作差即为答案。前式的最小值很好求，我们只要在 $c$ 的范围内枚举亮度增量即可。而后面这个式子比较麻烦。

对于式子 $\sum\limits_{i=0}^{n-1}x_iy_{(i+p)mod~n}$ 我们试着将第二个手环翻转，即 $y_{-i}=y_i\pmod{n}$ ，那么现在： $\sum\limits_{i=0}^{n-1}x_iy_{(-i+p)mod~n}=\sum\limits_{i=0}^{p}x_iy_{-i+p}+\sum\limits_{i=p+1}^{n-1}x_iy_{-i+p+n}$ 。这玩意不就是多项式卷积的第 $p$ 项和第 $p+n$ 项的系数么。卷积完枚举 $p$ 求个最小值就好了，美滋滋。

 //It is made by Awson on 2018.1.27

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <complex>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define dob complex<double>

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 #define writeln(x) (write(x), putchar('\n'))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int INF = ~0u>>;

 const double pi = acos(-1.0);

 const int N = 5e4*;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(int x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 int n, m, x, L, R[N+], tol, tolx, toly, s, c, tolxy, ans = INF;

 dob a[N+], b[N+];

 void FFT(dob *A, int o) {

     for (int i = ; i < n; i++) if (i > R[i]) swap(A[i], A[R[i]]);

     for (int i = ; i < n; i <<= ) {

         dob wn(cos(pi/i), sin(pi*o/i)), x, y;

         for (int j = ; j < n; j += (i<<)) {

             dob w(, );

             for (int k = ; k < i; k++, w *= wn) {

                 x = A[j+k], y = w*A[j+i+k];

                 A[j+k] = x+y, A[i+j+k] = x-y;

             }

         }

     }

 }

 void work() {

     read(n), read(c); s = n; n--;

     for (int i = ; i <= n; i++) read(x), a[i] = x, tol += x*x, tolx -= x;

     for (int i = n; i >= ; i--) read(x), b[i] = x, tol += x*x, tolx += x;

     m = *n;

     for (n = ; n <= m; n <<= ) L++;

     for (int i = ; i < n; i++) R[i] = (R[i>>]>>)|((i&)<<(L-));

     FFT(a, ), FFT(b, );

     for (int i = ; i <= n; i++) a[i] *= b[i];

     FFT(a, -);

     for (int i = ; i < s; i++) x = int(a[i].real()/n+0.5)+int(a[i+s].real()/n+0.5), tolxy = Max(tolxy, x);

     for (int i = -c; i <= c; i++) x = tol+tolx**i+i*i*s-*tolxy, ans = Min(ans, x);

     writeln(ans);

 }

 int main() {

     work();

     return ;

 }

相关文章