题解 P3723 【[AH2017/HNOI2017]礼物】

2018-03-11 12:48:04


(这应该是步骤最全的题解了233)
考虑到公式可能出问题,我就贴图片好了 (洛谷图床压了图,重新传一次)


推导过程

Formula

代码

#include <bits/stdc++.h>
#define PI M_PI
using namespace std;

typedef long long int64;

typedef std::complex<double> cmplx;

const int MAXN = 4e5;

namespace FFT {
    inline cmplx get_rt(int step, bool inv) {
        return !inv ? cmplx(cos(2*PI / step), sin(2*PI / step))
                    : cmplx(cos(2*PI / step), -sin(2*PI / step));
    }
    void fft(int len, cmplx* A, bool inv) {
        static int R[MAXN+10];
        for(int i = 1; i < len; i++)
            R[i] = ((R[i>>1]>>1) | (len>>(i&1))) & (len-1);
        for(int i = 0; i < len; i++)
            if(R[i] > i) swap(A[i], A[R[i]]);
        for(int step = 1; step < len; step <<= 1)
            for(int i = 0; i < len; i += (step<<1)) {
                cmplx omega = 1, rt = get_rt(step<<1, inv);
                for(int j = 0; j < step; j++, omega *= rt) {
                    cmplx t = omega * A[i+j+step];
                    A[i+j+step] = A[i+j] - t;
                    A[i+j] = A[i+j] + t;
                }
            }
        if(inv)
            for(int i = 0; i < len; i++) A[i] /= len;
    }
    void conv(int64* A, int64* B, int64* C, int deg) {
        static cmplx CA[MAXN+10], CB[MAXN+10], CC[MAXN+10];
        int len;
        for(len = 1; len <= ((deg + 1) << 1); len <<= 1);
        fill(CA, CA + len, 0);
        fill(CB, CB + len, 0);
        fill(CC, CC + len, 0);
        for(int i = 0; i <= deg; i++) {
            CA[i] = A[i], CB[i] = B[i];
        }
        fft(len, CA, false); fft(len, CB, false);
        for(int i = 0; i < len; i++)
            CC[i] = CA[i] * CB[i];
        fft(len, CC, true);
        for(int i = 0; i < len; i++)
            C[i] = int64(real(CC[i]) + 0.5);
    }
}

using FFT::conv;
int64 n, m, SumY, SumY2, SumC, SumC2, C[MAXN+10], Y[MAXN+10], T[MAXN+10];

inline int readint() {
    int f=1, r=0; char c=getchar();
    while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
    while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
    return f*r;
}

void Init() {
    n = readint(); m = readint();
    for(int i = 0; i < n; i++) C[i] = C[i+n] = readint();
    for(int i = 1; i <= n; i++) Y[i] = readint();
    reverse(C, C+n); reverse(C+n, C+2*n);
    conv(C, Y, T, 2*n);
    for(int i = 1; i <= n; i++) {
        SumY += Y[i];
        SumY2 += Y[i] * Y[i];
    }
    for(int i = 0; i < n; i++) {
        SumC += C[i];
        SumC2 += C[i] * C[i];
    }
}

void Work() {
    int64 Ans = LLONG_MAX;
    for(int a = 0; a <= n-1; a++) {
        int64 CurP, CurAns = LLONG_MAX, CoeA, CoeB, CoeC;
        CoeA = n;
        CoeB = 2*SumC - 2*SumY;
        CoeC = SumY2 + SumC2 - 2*T[n + a];
        CurP = (-CoeB) / (2*CoeA);
        for(int P = max(-m, CurP - 10); P <= min(m, CurP + 10); ++P)
            CurAns = min(CurAns, CoeA * P * P + CoeB * P + CoeC);
        Ans = min(Ans, CurAns);
    }
    cout << Ans;
}

int main() {
    Init(); Work();
    return 0;
}