| 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; |
| 21 | len <<= 1; |
| 22 | cpx w = exp(-2.0L * pi / n * cpx(0,1)), |
| 23 | *c = new cpx[n], *a = new cpx[len], |
| 24 | *b = new cpx[len]; |
| 25 | rep(i,0,n) c[i] = pow(w, (inv ? -1.0 : 1.0)*i*i/2); |
| 26 | rep(i,0,n) a[i] = x[i] * c[i], b[i] = 1.0L/c[i]; |
| 27 | rep(i,0,n-1) b[len - n + i + 1] = 1.0L/c[n-i-1]; |
| 28 | fft(a, len); fft(b, len); |
| 29 | rep(i,0,len) a[i] *= b[i]; |
| 30 | fft(a, len, true); |
| 31 | rep(i,0,n) { |
| 32 | x[i] = c[i] * a[i]; |
| 33 | if (inv) x[i] /= cpx(n); } |
| 34 | delete[] a; |
| 35 | delete[] b; |
| 36 | delete[] c; } |
| 37 | // vim: cc=60 ts=2 sts=2 sw=2: |