let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

POST2 - A cộng B version 2

main.cpp
Open in Github Download
#include <cmath>
#include <iostream>
using namespace std;

#define rep(i, a, b) for(int i=a; i<b; i++)

const int S = 18;
const int N = 1<<S;

struct complex {
    double r, i;
    complex(): r(0), i(0) {}
    complex(double t): r(cos(t)), i(sin(t)) {}
    complex(double r, double i): r(r), i(i) {}
    void operator/=(double d) {
        this->r /= d;
        this->i /= d;
    }
};
complex operator+(complex a, complex b) {
    a.r += b.r;
    a.i += b.i;
    return a;
}
complex operator-(complex a, complex b) {
    a.r -= b.r;
    a.i -= b.i;
    return a;
}
complex operator*(complex a, complex b) {
    return complex(a.r*b.r - a.i*b.i, a.r*b.i + a.i*b.r);
}

int reverse(int n) {
    int r = 0;
    rep(i, 0, S) r |= ((n & (1<<i))>>i)<<(S - i - 1);
    return r;
}

complex* fft(complex *a, bool inv=false) {
    complex *b = new complex[N];
    rep(i, 0, N) b[i] = a[reverse(i)];
    rep(s, 0, S) {
        int len = 1 << s;
        complex w((inv? 1:-1) * M_PI / len);
        int i = 0, j = 0;
        for (int count = N >> (s + 1); count--;) {
            i = j;
            j = i + len;
            complex t(1.0, 0);
            for (int l=len; l--;) {
                a[i] = b[i] + t*b[j];
                a[j] = b[i] - t*b[j];
                t = t * w;
                i++, j++;
            }
        }
        swap(a, b);
    }
    delete[] a;
    if (inv)  rep(i,0,N) b[i] /= N;
    return b;
}

template<class T> T read() {
    T t; cin >> t; return t;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m = read<int>();
    complex *a = new complex[N];
    complex *b = new complex[N];
    rep(i,0,m) a[read<int>() + 50000].r += 1.0;
    rep(i,0,m) b[read<int>() + 50000].r += 1.0;
    a = fft(a);
    b = fft(b);
    rep(i,0,N) a[i] = a[i] * b[i];
    a = fft(a, true);
    long long kq = 0;
    rep(i,0,m) kq += round(a[read<int>() + 100000].r);
    cout << kq;
    delete[] a;
    delete[] b;
    return 0;
}
Comments