fft

#define comp complex<double>
void fft(vector<comp>&a, bool inv) {
    int n = a.size();
    if (n == 1) {
        return;
    }

    vector<comp> a0(n / 2), a1(n / 2);
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }
    fft(a0, 0);
    fft(a1, 0);

    double angle = 2 * M_PI / n;
    comp w(1), wn(cos(angle), sin(angle));

    for (int i = 0; i < n / 2; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        w *= wn;
    }

    if (inv) {
        for (int i = 0; i < n; i++) a[i] /= n;
        reverse(++a.begin(), a.end());
    }
}