fork(7) download

///FFT

typedef complex<ld> cld;
complex<ld> a[MAXN], ya[MAXN], yb[MAXN], yt[MAXN], a1[MAXN], a2[MAXN];

/// a->y, sign = 1 | y->a, sign = -1
void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
    if(n <= 1) {
        y[q] = a[p]; return;
    }
    complex<ld> en = exp(complex<ld>(0, sign*2*PI/n));
    complex<ld> e = 1;
    fft(a, y, n/2, sign, p, s*2, q);
    fft(a, y, n/2, sign, p + s, s*2, q + n/2);
    REP(i, 0, n/2) {
        yt[i] = y[q+i] + e * y[q+n/2+i];
        yt[i+n/2] = y[q+i] - e * y[q+n/2+i];
        e *= en;
    }
    REP(i, 0, n) y[q+i] = yt[i];
}

void multiply(cld a[], cld b[], cld res[], int n) {
    fft(a, ya, n);
    fft(b, yb, n);
    REP(i, 0, n) ya[i] *= yb[i];
    fft(ya, res, n, -1);
    REP(i, 0, n) res[i] = llroundl(real(yb[i])/n);
}

prog.cpp:3:9: error: ‘complex’ does not name a type
 typedef complex<ld> cld;
         ^
prog.cpp:4:1: error: ‘complex’ does not name a type
 complex<ld> a[MAXN], ya[MAXN], yb[MAXN], yt[MAXN], a1[MAXN], a2[MAXN];
 ^
prog.cpp:7:10: error: variable or field ‘fft’ declared void
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
          ^
prog.cpp:7:10: error: ‘complex’ was not declared in this scope
prog.cpp:7:18: error: ‘ld’ was not declared in this scope
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                  ^
prog.cpp:7:22: error: ‘a’ was not declared in this scope
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                      ^
prog.cpp:7:24: error: expected primary-expression before ‘]’ token
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                        ^
prog.cpp:7:27: error: ‘complex’ was not declared in this scope
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                           ^
prog.cpp:7:35: error: ‘ld’ was not declared in this scope
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                   ^
prog.cpp:7:39: error: ‘y’ was not declared in this scope
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                       ^
prog.cpp:7:41: error: expected primary-expression before ‘]’ token
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                         ^
prog.cpp:7:44: error: expected primary-expression before ‘int’
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                            ^
prog.cpp:7:51: error: expected primary-expression before ‘int’
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                                   ^
prog.cpp:7:65: error: expected primary-expression before ‘int’
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                                                 ^
prog.cpp:7:76: error: expected primary-expression before ‘int’
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                                                            ^
prog.cpp:7:87: error: expected primary-expression before ‘int’
 void fft(complex<ld> a[], complex<ld> y[], int n, int sign = 1, int p = 0, int s = 1, int q = 0) {
                                                                                       ^

Standard output is empty