| 34 | #include "fft_implementation_modular_arithmetic.h" |
| 35 | |
| 36 | vector<int> multiply(vector<int> a, vector<int> b) { |
| 37 | int n = root_pw; |
| 38 | a.resize(root_pw); |
| 39 | b.resize(root_pw); |
| 40 | |
| 41 | fft(a, false); |
| 42 | fft(b, false); |
| 43 | for (int i = 0; i < n; i++) |
| 44 | a[i] = (int)(1LL * a[i] * b[i] % mod); |
| 45 | fft(a, true); |
| 46 | |
| 47 | return a; |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | int main() { |