SCUT - 271 - CC 非诚勿扰

https://scut.online/p/271

第一次遇到没这么裸的，其实感觉到是卷积但是不知道怎么化。看来以后要多注意下标。
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e6;

const double PI = acos(-1.0);

struct Complex {

    double x, y;

    Complex() {}

    Complex(double x, double y): x(x), y(y) {}

    friend Complex operator+(const Complex &a, const Complex &b) {

        return Complex(a.x + b.x, a.y + b.y);

    }

    friend Complex operator-(const Complex &a, const Complex &b) {

        return Complex(a.x - b.x, a.y - b.y);

    }

    friend Complex operator*(const Complex &a, const Complex &b) {

        return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);

    }

} A[MAXN + 5], B[MAXN + 5];

void FFT(Complex a[], int n, int op) {

    for(int i = 1, j = n >> 1; i < n - 1; ++i) {

        if(i < j)

            swap(a[i], a[j]);

        int k = n >> 1;

        while(k <= j) {

            j -= k;

            k >>= 1;

        }

        j += k;

    }

    for(int len = 2; len <= n; len <<= 1) {

        Complex wn(cos(2.0 * PI / len), sin(2.0 * PI / len)*op);

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

            Complex w(1.0, 0.0);

            for(int j = i; j < i + (len >> 1); ++j) {

                Complex u = a[j], t = a[j + (len >> 1)] * w ;

                a[j] = u + t, a[j + (len >> 1)] = u - t;

                w = w * wn;

            }

        }

    }

    if(op == -1) {

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

            a[i].x = (int)(a[i].x / n + 0.5);

    }

}

int pow2(int x) {

    int res = 1;

    while(res < x)

        res <<= 1;

    return res;

}

void convolution(Complex A[], Complex B[], int Asize, int Bsize) {

    int n = pow2(Asize + Bsize - 1);

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

        A[i].y = 0.0;

        B[i].y = 0.0;

    }

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

        A[i].x = 0;

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

        B[i].x = 0;

    FFT(A, n, 1);

    FFT(B, n, 1);

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

        A[i] = A[i] * B[i];

    FFT(A, n, -1);

    return;

}

ll ans[MAXN+5],ans0;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int n, m;

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

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

        scanf("%lf", &A[i].x);

    }

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

        scanf("%lf", &B[i].x);

    }

    reverse(B,B+n);

    convolution(A, B, n, n);

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

        ans[i]=(ll)round(A[i].x);

        //printf("%lld\n",ans[i]);

    }

    while(m--){

        int k;

        scanf("%d",&k);

        if(k==0)

            printf("%lld\n",ans[n-1]);

        else

            printf("%lld\n",ans[n-1-k]+ans[n-1+k]);

    }

    return 0;

}
巴特西

SCUT - 271 - CC 非诚勿扰 - FFT

最新文章

热门文章
