bzoj 4827: [HNOI2017]礼物 （FFT)

一道FFT

然而据说暴力可以水70分

然而我省选的时候看到了直接吓傻了  连暴力都没打

太弱了啊QAQ

emmmm

详细的拆开就看其他题解吧233

最后那一步卷积其实我一直没明白

后来画画图终于懂了

只要把其中一个反过来

多项式乘法的结果中的每一项系数就对应某一个Σx[i] * y[j] 的结果

前面几项是不完全的结果

但是太小了就被忽略啦

代码如下

/**************************************************************

    Problem: 4827

    User: cminus

    Language: C++

    Result: Accepted

    Time:5644 ms

    Memory:24568 kb

****************************************************************/

#include <cstdio>

#include <cmath>

#include <complex>

using namespace std;

const int N = ;

typedef long long ll;

typedef complex<double> cp;

const double pi = acos(-1.0);

cp A[N], B[N];

void FFT(cp *y, int n, int type) {

    if (n == ) return ;

    cp l[n >> ], r[n >> ];

    for (int i = ; i <= n; i++)

        if (i & )  r[i >> ] = y[i];

        else    l[i >> ] = y[i];

    FFT(l, n >> , type); FFT(r, n >> , type);

    cp omegan(cos( * pi / n), sin( * pi * type / n)), omega(, );

    for (int i = ; i < n >> ; i++) {

        y[i] = l[i] + r[i] * omega;

        y[i + (n >> )] = l[i] - r[i] * omega;

        omega *= omegan;

    }

}

int main() {

    int n, m, ans = , y = ;

    scanf("%d %d", &n, &m);

    for (int i = ; i < n; i++) {

        int x; scanf("%d", &x);

        A[n - i - ] = x;

        ans += x * x;

    }

    for (int i = ; i < n; i++) {

        int x; scanf("%d", &x);

        B[i] = x;

        ans += x * x;

        y += (int)B[i].real() - A[n - i - ].real();

    }

    int n1;  for (n1 = ; n1 <= n * ; n1 <<= );

    for (int i = ; i < n; i++)

        B[i + n] = B[i];

    FFT(A, n1, ); FFT(B, n1, );

    for (int i = ; i <= n1; i++)

        A[i] *= B[i];

    FFT(A, n1, -);

    int temp = , z = (-y) / n;

    for (int i = ; i < n; i++)  temp = max(temp, (int)(A[i + n - ].real() / n1 + 0.5));

    ans -= temp * ;

    temp = z * z * n + y * z * ;

    z += ; temp = min(temp, z * z * n + y * z * );

    z -= ; temp = min(temp, z * z * n + y * z * );

// 有理有据的精度优化

    ans += temp;

    printf("%d\n", ans);

    return ;

}