NOTE: n must be a power of two
| 2 | typedef complex<long double> cpx; |
| 3 | // NOTE: n must be a power of two |
| 4 | void fft(cpx *x, int n, bool inv=false) { |
| 5 | for (int i = 0, j = 0; i < n; i++) { |
| 6 | if (i < j) swap(x[i], x[j]); |
| 7 | int m = n>>1; |
| 8 | while (1 <= m && m <= j) j -= m, m >>= 1; |
| 9 | j += m; } |
| 10 | for (int mx = 1; mx < n; mx <<= 1) { |
| 11 | cpx wp = exp(cpx(0, (inv ? -1 : 1) * pi / mx)), w = 1; |
| 12 | for (int m = 0; m < mx; m++, w *= wp) { |
| 13 | for (int i = m; i < n; i += mx << 1) { |
| 14 | cpx t = x[i + mx] * w; |
| 15 | x[i + mx] = x[i] - t; |
| 16 | x[i] += t; } } } |
| 17 | if (inv) rep(i,0,n) x[i] /= cpx(n); } |
| 18 | void czt(cpx *x, int n, bool inv=false) { |
| 19 | int len = 2*n+1; |
| 20 | while (len & (len - 1)) len &= len - 1; |