| 20 | } |
| 21 | }; |
| 22 | void fft(vector<base> &p, bool inv = 0) { |
| 23 | int n = p.size(), i = 0; |
| 24 | for(int j = 1; j < n - 1; ++j) { |
| 25 | for(int k = n >> 1; k > (i ^= k); k >>= 1); |
| 26 | if(j < i) swap(p[i], p[j]); |
| 27 | } |
| 28 | for(int l = 1, m; (m = l << 1) <= n; l <<= 1) { |
| 29 | double ang = 2 * PI / m; |
| 30 | base wn = base(cos(ang), (inv ? 1. : -1.) * sin(ang)), w; |
| 31 | for(int i = 0, j, k; i < n; i += m) { |
| 32 | for(w = base(1, 0), j = i, k = i + l; j < k; ++j, w = w * wn) { |
| 33 | base t = w * p[j + l]; |
| 34 | p[j + l] = p[j] - t; |
| 35 | p[j] = p[j] + t; |
| 36 | } |
| 37 | } |
| 38 | } |
| 39 | if(inv) for(int i = 0; i < n; ++i) p[i].a /= n, p[i].b /= n; |
| 40 | } |
| 41 | vector<int> multiply(vector<int> &a, vector<int> &b) { |
| 42 | int n = a.size(), m = b.size(), t = n + m - 1, sz = 1; |
| 43 | while(sz < t) sz <<= 1; |