| 53 | vector<long long int> A1(MAX),A2(MAX); |
| 54 | |
| 55 | void fft(vector<cd> & a, bool invert) { |
| 56 | int n = a.size(); |
| 57 | |
| 58 | for (int i = 1, j = 0; i < n; i++) { |
| 59 | int bit = n >> 1; |
| 60 | for (; j & bit; bit >>= 1) |
| 61 | j ^= bit; |
| 62 | j ^= bit; |
| 63 | |
| 64 | if (i < j) |
| 65 | swap(a[i], a[j]); |
| 66 | } |
| 67 | |
| 68 | for (int len = 2; len <= n; len <<= 1) { |
| 69 | double ang = 2 * PI / len * (invert ? -1 : 1); |
| 70 | cd wlen(cos(ang), sin(ang)); |
| 71 | for (int i = 0; i < n; i += len) { |
| 72 | cd w(1); |
| 73 | for (int j = 0; j < len / 2; j++) { |
| 74 | cd u = a[i+j], v = a[i+j+len/2] * w; |
| 75 | a[i+j] = u + v; |
| 76 | a[i+j+len/2] = u - v; |
| 77 | w *= wlen; |
| 78 | } |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | if (invert) { |
| 83 | for (cd & x : a) |
| 84 | x /= n; |
| 85 | } |
| 86 | } |
| 87 | void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){ |
| 88 | for(int i=0;i<a.size();i++){ |
| 89 | c[i]=a[i]*b[i]; |