题解 P3723 【[AH2017/HNOI2017]礼物】
panda_2134
2018-03-11 12:48:04
（这应该是步骤最全的题解了233）
考虑到公式可能出问题，我就贴图片好了
（洛谷图床压了图，重新传一次)
-------------------
## 推导过程
## 代码
```cpp
#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;
}
```