[bzoj 4827] [Hnoi2017]礼物

两个n颗珠子的手镯, 每颗珠子有亮度 ([1,m]上的整数). 手镯可以旋转, 不能翻转. 可以将其中一个手镯的所有珠子的亮度同时增加一个自然数. 求对应位置亮度的最小方差. (n≤5*10^4, m≤100) 对于方差而言, 将一个镯子的亮度增加一个自然数, 等价于将另一个镯子的亮度减少一个自然数.

设第一个镯子亮度的改变量为, 旋转后第一个镯子的原亮度依次为, 旋转后第二个镯子的原亮度一次为, 则

记

那么

这是一个开口向上的定义在全体整数上的二次函数. 注意到是常量, 所以最小值总在处取得. 只需求

考试的时候, 推到这一步, 感到奥妙重重......这是一个点积, 把其中一个数列倒过来就是卷积, 还是循环卷积. 循环卷积貌似有专门的算法? 可是我不会啊......算了70分拉倒......

所以说, 一知半解比啥都不知道更可怕......

循环卷积

把两个线性卷积加起来就是循环卷积了......所以, 把y倒过来, 和x卷一下, 把x倒过来, 和y卷一下, 就解决问题了......

或者, 把x^{i的系数和x}(i+n)的系数加起来. 之前没想到.

typedef complex<double> Complex;

const double pi = acos(-1);
const int N = (1<<18) + 2;

namespace Convol {	
	int n, rev[N];
	
	inline void init(int _n, int s)
	{
		n = _n;
		--s;
		rep (i, 1, n)
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);
	}

	void fft(Complex a[], int d=1)
	{
		rep (i, 0, n)
			if (rev[i] < i)
				swap(a[i], a[rev[i]]);

		for (int m = 1; m < n; m <<= 1) {
			Complex _w(cos(pi/m), d * sin(pi/m));
			for (int j = 0; j < n; j += m<<1) {
				Complex w(1);
				rep (k, 0, m) {
					Complex t = w * a[j+m+k];
					a[j+m+k] = a[j+k] - t;
					a[j+k] += t;
					w *= _w;
				}
			}
		}

		if (d == -1)
			rep (i, 0, n) a[i] /= n;
	}

	void convol(int a[], int b[], int c[])
	{
		static Complex x[N], y[N];
		rep (i, 0, n)
			x[i] = Complex(a[i], b[i]);
		fft(x);
		rep (i, 0, n) {
			int j = (n-i) & (n-1);
			y[i] = Complex(0, 0.25) * (conj(x[j]*x[j]) - x[i]*x[i]);
		}
		fft(y, -1);
		rep (i, 0, n)
			c[i] = round(real(y[i]));
	}
}

using Convol::convol;

int a[2][N], b[2][N], c[2][N];

int main()
{	
	int n, m, l = 1, s = 0, u = 0, v = 0;
	scanf("%d%d", &n, &m);
	while (l < 2*n-1) l <<= 1, ++s;
	
	rep (i, 0, n) {
		scanf("%d", a[0]+i);
		a[1][n-1-i] = a[0][i];
		u += a[0][i];
		v += a[0][i] * a[0][i];
	}
	rep (i, 0, n) {
		scanf("%d", b[0]+i);
		b[1][n-1-i] = b[0][i];
		u -= b[0][i];
		v += b[0][i] * b[0][i];
	}

	Convol::init(l, s);
	convol(a[0], b[1], c[0]);
	convol(a[1], b[0], c[1]);

	int z = round((double)-u/n), ans = c[0][n-1];
	rep (i, 0, n-1)
		ans = max(ans, c[0][i] + c[1][n-i-2]);
	printf("%lld\n", (long long)n*z*z + 2*z*u + v - 2*ans);

	return 0;
}