diff options
Diffstat (limited to 'content/math/transforms/multiplyFFT.cpp')
| -rw-r--r-- | content/math/transforms/multiplyFFT.cpp | 12 |
1 files changed, 12 insertions, 0 deletions
diff --git a/content/math/transforms/multiplyFFT.cpp b/content/math/transforms/multiplyFFT.cpp new file mode 100644 index 0000000..0022d1f --- /dev/null +++ b/content/math/transforms/multiplyFFT.cpp @@ -0,0 +1,12 @@ +vector<ll> mul(vector<ll>& a, vector<ll>& b) { + int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); + vector<cplx> a2(all(a)), b2(all(b)); + a2.resize(n), b2.resize(n); + fft(a2), fft(b2); + for (int i=0; i<n; i++) a2[i] *= b2[i]; + fft(a2, true); + + vector<ll> ans(n); + for (int i=0; i<n; i++) ans[i] = llround(a2[i].real()); + return ans; +} |