我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一
个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突
然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有
装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，
但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差
异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，
其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手 环的 i 号位置装饰物
亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： $sumlimits_{i=1}^{n}(x_i-y_i)^2$ 麻烦你帮他
计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？
$nleq 50000,m leq 100$
sol：
首先根据 GXZlegend 大神的数学推理得到 $c = frac{sum x - sum y}{n}$
大概是有两个环，要求最大的 $sumlimits_{i=1}^n x_i imes y_i$
直接把 $y$ 翻转过来做个卷积，然后看 $nsim 2n$ 项哪个最小就行了
#include<bits/stdc++.h> #define LL long long #define DB long double #define rep(i, s, t) for(register LL i = (s), i##end = (t); i <= i ## end; ++i) #define dwn(i, s, t) for(register LL i = (s), i##end = (t); i >= i ## end; --i) using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); for(;!isdigit(ch);ch=getchar())if(ch == '-') f=-f; for(;isdigit(ch);ch=getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 500010; const DB pi = acos(-1); struct cp { DB x, y; cp(){} cp(DB _1, DB _2) : x(_1), y(_2){} cp operator + (const cp &b) const { return cp(x + b.x, y + b.y); } cp operator - (const cp &b) const { return cp(x - b.x, y - b.y); } cp operator * (const cp &b) const { return cp(x * b.x - y * b.y, x * b.y + y * b.x); } }cu[maxn], cv[maxn]; int r[maxn], lg[maxn + maxn], a[maxn], b[maxn]; void fft(cp *a, int n, int f) { rep(i, 1, n-1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lg[n] - 1)); rep(i, 1, n-1) if(i < r[i]) swap(a[i], a[r[i]]); for(int i=1;i<n;i<<=1) { cp wn = cp(cos(pi / i), f * sin(pi / i)); for(int j=0;j<n;j+=(i<<1)) { cp w = cp(1, 0); for(int k=0;k<i;k++,w=w*wn) { cp x = a[j + k], y = w * a[j + k + i]; a[j + k] = x + y; a[j + k + i] = x - y; } } } //if(f == -1) rep(i, 0, n-1) a[i].x = round(a[i].x / (DB)n); } int n, m; int main() { DB sumx = 0.0, sumy = 0.0; lg[0] = -1; rep(i, 1, 500000) lg[i] = lg[i >> 1] + 1; n = read(), m = read(); DB c = 0.0; rep(i, 0, n-1) a[i] = read(), c -= a[i]; rep(i, 0, n-1) b[i] = read(), c += b[i]; c = round(c / n); rep(i, 0, n-1) sumx += 1.0 * (a[i] + c) * (a[i] + c), sumy += 1.0 * b[i] * b[i]; rep(i, 0, n + n - 1) cu[i].x = a[i % n] + c; rep(i, 0, n - 1) cv[i].x = b[n - i - 1]; int len = 1; for(;len <= n+n; len <<= 1); fft(cu, len, 1); fft(cv, len, 1); rep(i, 0, len) cu[i] = cu[i] * cv[i]; fft(cu, len, -1); DB ans = 1e15; rep(i, n-1, n + n - 1) ans = min(ans, sumx + sumy - 2 * round(cu[i].x / (DB)len)); double res = ans; printf("%.0f ", res); }
因为本题值域很小，NTT 也能过
#include<bits/stdc++.h> #define LL long long #define rep(i, s, t) for(register LL i = (s), i##end = (t); i <= i ## end; ++i) #define dwn(i, s, t) for(register LL i = (s), i##end = (t); i >= i ## end; --i) using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); for(;!isdigit(ch);ch=getchar())if(ch == '-') f=-f; for(;isdigit(ch);ch=getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 500010, mod = 998244353; inline int ksm(int x, int t) { int res = 1; while(t) { if(t & 1) res = 1LL * res * x % mod; x = 1LL * x * x % mod; t = t >> 1; } return res; } int cu[maxn], cv[maxn]; int r[maxn], lg[maxn + maxn], a[maxn], b[maxn]; void fft(int *a, int n, int f) { rep(i, 1, n-1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lg[n] - 1)); rep(i, 1, n-1) if(i < r[i]) swap(a[i], a[r[i]]); for(int i=1;i<n;i<<=1) { int wn = ksm(3, (mod-1) / (i << 1)); if(f == -1) wn = ksm(wn, mod - 2); for(int j=0;j<n;j+=(i<<1)) { int w = 1; for(int k=0;k<i;k++,w=1LL*w*wn%mod) { int x = a[j + k], y = 1LL * w * a[j + k + i] % mod; a[j + k] = (x + y) % mod; a[j + k + i] = (x - y + mod) % mod; } } } if(f == -1) { int inv_n = ksm(n, mod - 2); rep(i, 0, n-1) a[i] = 1LL * a[i] * inv_n % mod; } } int n, m; int main() { int sumx = 0, sumy = 0; lg[0] = -1; rep(i, 1, 500000) lg[i] = lg[i >> 1] + 1; n = read(), m = read(); int c = 0; rep(i, 0, n-1) a[i] = read(), c -= a[i]; rep(i, 0, n-1) b[i] = read(), c += b[i]; c = round(1.0 * c / n); //cout << c << endl; rep(i, 0, n-1) sumx += (a[i] + c) * (a[i] + c), sumy += b[i] * b[i]; rep(i, 0, n + n - 1) cu[i] = a[i % n] + c; rep(i, 0, n - 1) cv[i]= b[n - i - 1]; int len = 1; for(;len <= n+n; len <<= 1); fft(cu, len, 1); fft(cv, len, 1); rep(i, 0, len) cu[i] = 1LL * cu[i] * cv[i] % mod; fft(cu, len, -1); int ans = 1e9; rep(i, n-1, n + n - 1) ans = min(ans, sumx + sumy - 2 * cu[i]); cout << ans << endl; }