renamed ntt and bitwiseConv function + more multiply functions

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;
diff --git a/tcr.pdf b/tcr.pdf
index 6404502..e7330c0 100644
--- a/tcr.pdf
+++ b/tcr.pdf