| 324 | } |
| 325 | |
| 326 | void fft(vector<Cplx>& a, bool invert) const { |
| 327 | int n = a.size(); |
| 328 | for (int i = 1, j = 0; i < n; ++i) { |
| 329 | int bit = n / 2; |
| 330 | for (; j >= bit; bit /= 2) j -= bit; |
| 331 | j += bit; |
| 332 | if (i < j) swap(a[i], a[j]); |
| 333 | } |
| 334 | for (int len = 2; len <= n; len *= 2) { |
| 335 | ld ang = 2 * PI / len * (invert ? -1 : 1); |
| 336 | Cplx wlen = polar(1, ang); |
| 337 | for (int i = 0; i < n; i += len) { |
| 338 | Cplx w(1); |
| 339 | for (int j = 0; j < len / 2; ++j) { |
| 340 | Cplx u = a[i + j], v = a[i + j + len / 2] * w; |
| 341 | a[i + j] = u + v; |
| 342 | a[i + j + len / 2] = u - v; |
| 343 | w *= wlen; |
| 344 | } |
| 345 | } |
| 346 | } |
| 347 | if (invert) for (int i = 0; i < n; ++i) a[i] /= n; |
| 348 | } |
| 349 | void multiply_fft(const vector<int> &a, const vector<int> &b, vector<int> &res) const { |
| 350 | vector<Cplx> fa(a.begin(), a.end()), fb(b.begin(), b.end()); |
| 351 | int n = 1; |