以前看到过，但是搞不倒。知道了算法之后就好搞了。
题意：给定两个长为n的序列，你可以把某个序列全部加上某个数c，变成循环同构序列。
求你操作后的min∑(ai - bi)²
解：
设加上的数为c，那么得到一个柿子：∑(ai - bi + c)²
拆开：∑ai2 + ∑bi2 - 2∑aibi + nc² + 2c∑(ai - bi)
发现其中前两项是常数不用管。第三项是卷积，后两项是关于c的二次函数。
于是后两项用二次函数的对称轴直接搞出来。第三项构造函数卷积，看哪个位置的值最大即可。
具体来说，把a复制成两倍，反转b。然后卷积出来的第n ~ 2n项就是。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 300010; 7 const double pi = 3.1415926535897932384626; 8 const LL INF = 0x3f3f3f3f3f3f3f3f; 9 10 struct cp { 11 double x, y; 12 cp(double X = 0, double Y = 0) { 13 x = X; 14 y = Y; 15 } 16 inline cp operator +(const cp &w) const { 17 return cp(x + w.x, y + w.y); 18 } 19 inline cp operator -(const cp &w) const { 20 return cp(x - w.x, y - w.y); 21 } 22 inline cp operator *(const cp &w) const { 23 return cp(x * w.x - y * w.y, x * w.y + y * w.x); 24 } 25 }a[N], b[N]; 26 27 int r[N]; 28 LL A[N], B[N]; 29 30 inline void FFT(int n, cp *a, int f) { 31 for(int i = 0; i < n; i++) { 32 if(i < r[i]) { 33 std::swap(a[i], a[r[i]]); 34 } 35 } 36 for(int len = 1; len < n; len <<= 1) { 37 cp Wn(cos(pi / len), f * sin(pi / len)); 38 for(int i = 0; i < n; i += (len << 1)) { 39 cp w(1, 0); 40 for(int j = 0; j < len; j++) { 41 cp t = a[i + len + j] * w; 42 a[i + len + j] = a[i + j] - t; 43 a[i + j] = a[i + j] + t; 44 w = w * Wn; 45 } 46 } 47 } 48 if(f == -1) { 49 for(int i = 0; i <= n; i++) { 50 a[i].x /= n; 51 } 52 } 53 return; 54 } 55 56 int main() { 57 int n, m; 58 LL XX = 0, YY = 0, SX = 0, SY = 0; 59 scanf("%d%d", &n, &m); 60 n--; 61 for(int i = 0; i <= n; i++) { 62 scanf("%lld", &A[i]); 63 SX += A[i]; 64 XX += A[i] * A[i]; 65 a[i].x = a[i + n + 1].x = A[i]; 66 } 67 for(int i = 0; i <= n; i++) { 68 scanf("%lld", &B[i]); 69 SY += B[i]; 70 YY += B[i] * B[i]; 71 b[n - i].x = B[i]; 72 } 73 int len = 2, lm = 1; 74 while(len <= n * 3) { 75 len <<= 1; 76 lm++; 77 } 78 for(int i = 1; i <= len; i++) { 79 r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lm - 1)); 80 } 81 82 FFT(len, a, 1); 83 FFT(len, b, 1); 84 for(int i = 0; i <= len; i++) { 85 a[i] = a[i] * b[i]; 86 } 87 FFT(len, a, -1); 88 89 LL ans = -INF; 90 for(int i = n; i <= n * 2; i++) { 91 ans = std::max(ans, (LL)(a[i].x + 0.5)); 92 } 93 94 double C = -1.0 * (SX - SY) / (n + 1); 95 LL c = (int)(C); 96 LL temp = std::min((n + 1) * c * c + 2 * (SX - SY) * c, (n + 1) * (c + 1) * (c + 1) + 2 * (SX - SY) * (c + 1)); 97 temp = std::min(temp, (n + 1) * (c - 1) * (c - 1) + 2 * (SX - SY) * (c - 1)); 98 99 printf("%lld\n", XX + YY - 2 * ans + temp);100 101 return 0;102 }