diff options
| -rw-r--r-- | math/transforms/bitwiseTransforms.cpp | 2 | ||||
| -rw-r--r-- | math/transforms/multiplyBitwise.cpp | 8 | ||||
| -rw-r--r-- | math/transforms/multiplyFFT.cpp (renamed from math/transforms/multiply.cpp) | 2 | ||||
| -rw-r--r-- | math/transforms/multiplyNTT.cpp | 8 | ||||
| -rw-r--r-- | math/transforms/ntt.cpp | 2 | ||||
| -rw-r--r-- | tcr.pdf | bin | 667072 -> 667178 bytes |
6 files changed, 19 insertions, 3 deletions
diff --git a/math/transforms/bitwiseTransforms.cpp b/math/transforms/bitwiseTransforms.cpp index 7d1f80d..28561da 100644 --- a/math/transforms/bitwiseTransforms.cpp +++ b/math/transforms/bitwiseTransforms.cpp @@ -1,4 +1,4 @@ -void fft(vector<ll>& a, bool inv = false) { +void bitwiseConv(vector<ll>& a, bool inv = false) { int n = sz(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { diff --git a/math/transforms/multiplyBitwise.cpp b/math/transforms/multiplyBitwise.cpp new file mode 100644 index 0000000..0fa671c --- /dev/null +++ b/math/transforms/multiplyBitwise.cpp @@ -0,0 +1,8 @@ +vector<ll> mul(vector<ll> a, vector<ll> b) { + int n = 1 << (__lg(max(sz(a), sz(b)) - 1) + 1); + a.resize(n), b.resize(n); + bitwiseConv(a), bitwiseConv(b); + for (int i=0; i<n; i++) a[i] *= b[i]; // MOD? + bitwiseConv(a, true); + return a; +} diff --git a/math/transforms/multiply.cpp b/math/transforms/multiplyFFT.cpp index 59c394e..0022d1f 100644 --- a/math/transforms/multiply.cpp +++ b/math/transforms/multiplyFFT.cpp @@ -1,5 +1,5 @@ vector<ll> mul(vector<ll>& a, vector<ll>& b) { - int n = 1 << (__lg(sz(a) + sz(b)) + 1); + 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); diff --git a/math/transforms/multiplyNTT.cpp b/math/transforms/multiplyNTT.cpp new file mode 100644 index 0000000..806d124 --- /dev/null +++ b/math/transforms/multiplyNTT.cpp @@ -0,0 +1,8 @@ +vector<ll> mul(vector<ll> a, vector<ll> b) { + int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); + a.resize(n), b.resize(n); + ntt(a), ntt(b); + for (int i=0; i<n; i++) a[i] = a[i] * b[i] % mod; + ntt(a, true); + return a; +} diff --git a/math/transforms/ntt.cpp b/math/transforms/ntt.cpp index 18d5bd8..ca605d3 100644 --- a/math/transforms/ntt.cpp +++ b/math/transforms/ntt.cpp @@ -1,6 +1,6 @@ constexpr ll mod = 998244353, root = 3; -void fft(vector<ll>& a, bool inv = false) { +void ntt(vector<ll>& a, bool inv = false) { int n = sz(a); auto b = a; ll r = inv ? powMod(root, mod - 2, mod) : root; Binary files differ |