【题解】P3723 [AH2017/HNOI2017]礼物（多项式，FFT，卷积）

P3723 [AH2017/HNOI2017]礼物

Des

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

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

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

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

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

\(\texttt{Data Range:}\)

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

Sol

把 \(x_i\) 加上 \(c\) 或 \(y_i\) 加上 \(c\) 等效于给 \(x_i-y_i\) 加上一个 \(t\in[-100,100]\)，然后再展开得到

\[\sum_{i=1}^n(x_i-y_i)^2+2t\left(\sum_{i=1}^nx_i-\sum_{i=1}^ny_i\right)+nt^2 \]

于是只用计算 \(\sum_{i=1}^n(x_i-y_i)^2\) 的最小值。由于可以旋转手环，于是把 \(F_i\) 表示为第一个手环向左转 \(i\) 个单位得到 \(\sum_{i=1}^n(x_i-y_i)\) 的值，有 \(F_i=\sum_{j=1}^i(y_j-x_{n-i+j})^2+\sum_{j=1}^{n-i}(y_i+j-x_j)^2\)，那么 \(\sum_{i=1}^n(x_i-y_i)^2\) 的最小值就是 \(\min_{i=0}^{n-1}F_i\)。令 \(y'_i=y_{n-i},x'_i=x_{n-i}\)，有

\[\begin{align*} F_i=&\sum_{j=1}^i(y_j^2+{x'}_{i-j}^2)-2\sum_{j=0}^iy_ix'_{i-j}\\ &+\sum_{j=1}^{n-i}({y'}_{n-i-j}^2+x_j^2)-2\sum_{j=0}^{n-i}{y'}_{n-i-j}x_j \end{align*} \]

式子里加上的部分恒等于 \(\sum_{i=1}^n(x_i^2+y_i^2)\)，减去的部分卷积算就行了。

题解里有一个简单的做法是把 \(\sum_{i=1}^n(x_i-y_i)^2\) 直接拆开来看，发现需要算的就是 \(\sum_{i=1}^nx_iy_i\) 的最大值。于是，他将数列 \(\{x\}\) 先翻转，再倍长，再与 \(\{y\}\) 做卷积。卷出来的第 \(n+1\) 项到第 \(2n\) 项的 \(\max\) 就是 \(\sum_{i=1}^n x_iy_i\) 的最大值。正确性很容易理解，但不太容易想到，姑且将其作为一个技巧记下来吧。

My code

#include 

using namespace std;
typedef long long ll;
const int N = 1.5e5 + 5;
int n, m;
const double pi = acos(-1);
struct cp {
	double x, y;
	cp(double _x = 0, double _y = 0) : x(_x), y(_y) {}
	cp operator+(const cp &b) { return cp(x + b.x, y + b.y); }
	cp operator-(const cp &b) { return cp(x - b.x, y - b.y); }
	cp operator*(const cp &b) {
		return cp(x * b.x - y * b.y, x * b.y + y * b.x);
	}
} a[N], b[N], a2[N], b2[N], LH[N], RH[N];
int rev[N], lim = 1, l;
double S, sub; // S 为 sum(x_i^2 + y_i^2)，sub 为 sum(x_i - y_i) 
void FFT(cp *F, int type) {
	for(int i = 0; i < lim; i++)
		if(i < rev[i]) swap(F[i], F[rev[i]]);
	for(int i = 1; i < lim; i <<= 1) {
		cp w1(cos(pi / i), type * sin(pi / i));
		for(int j = 0; j < lim; j += i << 1) {
			cp w(1, 0);
			for(int k = 0; k < i; k++, w = w * w1) {
				cp F1 = F[j + k], F2 = w * F[j + i + k];
				F[j + k] = F1 + F2, F[j + i + k] = F1 - F2;
			}
		}
	}
	if(type == -1) for(int i = 0; i < lim; i++)
		F[i].x /= lim, F[i].y /= lim;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].x, a2[n - i].x = a[i].x;
		S += a[i].x * a[i].x, sub += a[i].x;
	}
	for(int i = 1; i <= n; i++) {
		cin >> b[i].x, b2[n - i].x = b[i].x;
		S += b[i].x * b[i].x, sub -= b[i].x;
	}
	while(lim <= n + n) lim <<= 1, ++l;
	for(int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) + (i & 1) * (1 << (l - 1));
	FFT(a, 1), FFT(a2, 1), FFT(b, 1), FFT(b2, 1);
	for(int i = 0; i < lim; i++)
		LH[i] = a2[i] * b[i], RH[i] = a[i] * b2[i];
	FFT(LH, -1), FFT(RH, -1);
	double ans = 1e18, add = 1e18; // add 为式子里加上的部分的最小值 
	for(int j = -100; j <= 100; j++)
		add = min(add, S + (ll)2 * j * sub + (ll)n * j * j);
	for(int i = 0; i < n; i++)
		ans = min(ans, add - 2 * LH[i].x - 2 * RH[n - i].x);
	cout << (ll)(round(ans) + 0.1) << '\n';
	
	return 0;
}