eq = 0: 4 FFTs in total eq = 1: 3 FFTs in total
| 51 | //eq = 0: 4 FFTs in total |
| 52 | //eq = 1: 3 FFTs in total |
| 53 | vector<int> multiply(vector<int> &a, vector<int> &b, int eq = 0) { |
| 54 | int need = a.size() + b.size() - 1; |
| 55 | int p = 0; |
| 56 | while((1 << p) < need) p++; |
| 57 | ensure_base(p); |
| 58 | int sz = 1 << p; |
| 59 | vector<base> A, B; |
| 60 | if(sz > (int)A.size()) A.resize(sz); |
| 61 | for(int i = 0; i < (int)a.size(); i++) { |
| 62 | int x = (a[i] % mod + mod) % mod; |
| 63 | A[i] = base(x & ((1 << 15) - 1), x >> 15); |
| 64 | } |
| 65 | fill(A.begin() + a.size(), A.begin() + sz, base{0, 0}); |
| 66 | fft(A, sz); |
| 67 | if(sz > (int)B.size()) B.resize(sz); |
| 68 | if(eq) copy(A.begin(), A.begin() + sz, B.begin()); |
| 69 | else { |
| 70 | for(int i = 0; i < (int)b.size(); i++) { |
| 71 | int x = (b[i] % mod + mod) % mod; |
| 72 | B[i] = base(x & ((1 << 15) - 1), x >> 15); |
| 73 | } |
| 74 | fill(B.begin() + b.size(), B.begin() + sz, base{0, 0}); |
| 75 | fft(B, sz); |
| 76 | } |
| 77 | double ratio = 0.25 / sz; |
| 78 | base r2(0, - 1), r3(ratio, 0), r4(0, - ratio), r5(0, 1); |
| 79 | for(int i = 0; i <= (sz >> 1); i++) { |
| 80 | int j = (sz - i) & (sz - 1); |
| 81 | base a1 = (A[i] + conj(A[j])), a2 = (A[i] - conj(A[j])) * r2; |
| 82 | base b1 = (B[i] + conj(B[j])) * r3, b2 = (B[i] - conj(B[j])) * r4; |
| 83 | if(i != j) { |
| 84 | base c1 = (A[j] + conj(A[i])), c2 = (A[j] - conj(A[i])) * r2; |
| 85 | base d1 = (B[j] + conj(B[i])) * r3, d2 = (B[j] - conj(B[i])) * r4; |
| 86 | A[i] = c1 * d1 + c2 * d2 * r5; |
| 87 | B[i] = c1 * d2 + c2 * d1; |
| 88 | } |
| 89 | A[j] = a1 * b1 + a2 * b2 * r5; |
| 90 | B[j] = a1 * b2 + a2 * b1; |
| 91 | } |
| 92 | fft(A, sz); fft(B, sz); |
| 93 | vector<int> res(need); |
| 94 | for(int i = 0; i < need; i++) { |
| 95 | long long aa = A[i].x + 0.5; |
| 96 | long long bb = B[i].x + 0.5; |
| 97 | long long cc = A[i].y + 0.5; |
| 98 | res[i] = (aa + ((bb % mod) << 15) + ((cc % mod) << 30))%mod; |
| 99 | } |
| 100 | return res; |
| 101 | } |
| 102 | template <int32_t MOD> |
| 103 | struct modint { |
| 104 | int32_t value; |
no test coverage detected