[AH2017/HNOI2017]礼物 （FFT）

题面

LOJ传送门

题解

直接把贡献写出来看看。
\[\sum_{i=1}^n(a_i-b_i+x)^2=\sum_{i=1}^n(a_i^2+b_i^2)+nx^2+2x\sum_{i=1}^n(a_i-b_i)-2\sum_{i=1}^na_ib_i\]
发现当\(x\)已知时，唯一需要考虑的就是最后一项，因为可以循环位移数组。然后由于\(x\)值域\([-m,m]\)可枚举，那么问题就在于怎么求\(\max\sum_{i=1}^na_ib_i\)。

我们把\(a\)数组倍长，就是求\(\max_{i=1}^{n}\sum_{j=1}^na_{i+j-1}b_j\)

把\(b\)数组倒序，就是求\(\max_{i=1}^{n}\sum_{j=1}^na_{i+j-1}b_{n-j+1}\)

那么这就是一个卷积的形式，直接\(FFT\)乘起来求第\(n+1\)到\(2*n\)项的最大值就行了。最后再枚举\(x\)求答案。实际上不用枚举，直接二次函数对称轴，不过\(m\)只有\(100\)，随便做了。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = (1<<18) + 5;
const double Pi = acos(-1.0);
int n, m, a[MAXN], b[MAXN];
LL sa, sb, s2;
struct cp {
    double x, y;
    cp(){}
    cp(double xx, double yy):x(xx), y(yy){}
    inline cp operator+(const cp &o)const { return cp(x+o.x, y+o.y); }
    inline cp operator-(const cp &o)const { return cp(x-o.x, y-o.y); }
    inline cp operator*(const cp &o)const { return cp(x*o.x-y*o.y, x*o.y+y*o.x); }
}f[MAXN], g[MAXN];
int rev[MAXN];
void FFT(cp *arr, int len, int flg) {
    for(int i = 0; i < len; ++i)if(rev[i]<i)swap(arr[i], arr[rev[i]]);
    cp u, v, wn, w;
    for(int i = 2; i <= len; i<<=1) {
        wn = cp(cos(2*Pi/i*flg), sin(2*Pi/i*flg));
        for(int j = 0; j < len; j += i) {
            w = cp(1, 0);
            for(int k = j; k < j + i/2; ++k) {
                u = arr[k];
                v = arr[k+i/2]*w;
                arr[k] = u + v;
                arr[k+i/2] = u - v;
                w = w * wn;
            }
        }
    }
    if(flg == -1) for(int i = 0; i < len; ++i) arr[i].x/=len;
}
int main () {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), sa += a[i], s2 += a[i]*a[i], a[n+i] = a[i];
    for(int i = n; i >= 1; --i) scanf("%d", &b[i]), sb += b[i], s2 += b[i]*b[i];
    int len = 1; while(len <= (3*n)) len<<=1;
    for(int i = 1; i < len; ++i) rev[i] = (rev[i>>1]>>1)|((i&1)*(len>>1));
    for(int i = 0; i < len; ++i) f[i] = cp(a[i], 0), g[i] = cp(b[i], 0);
    FFT(f, len, 1), FFT(g, len, 1);
    for(int i = 0; i < len; ++i) f[i] = f[i] * g[i];
    FFT(f, len, -1);
    LL mx = 0, ans = 1ll<<50;
    for(int i = n+1; i <= 2*n; ++i)
        mx = max(mx, (LL)round(f[i].x));
    for(LL x = -m; x <= m; ++x)
        ans = min(ans, s2 + n*x*x + 2*x*(sa-sb) - 2*mx);
    printf("%lld\n", ans);
}