change fft, ntt and bitwise transforms

1 files changed, 6 insertions, 15 deletions

diff --git a/math/transforms/orTransform.cpp b/math/transforms/orTransform.cpp
index fdb5bb8..eb1da44 100644
--- a/math/transforms/orTransform.cpp
+++ b/math/transforms/orTransform.cpp
@@ -1,17 +1,8 @@
-void fft(vector<ll>& a, bool inverse = 0) {
+void fft(vector<ll>& a, bool inv = false) {
 	int n = sz(a);
-	for (int i = 0, j = 1; j < n - 1; ++j) {
-		for (int k = n >> 1; k > (i ^= k); k >>= 1);
-		if (j < i) swap(a[i], a[j]);
-	}
 	for (int s = 1; s < n; s *= 2) {
-		for (int j = 0; j < n; j+= 2 * s) {
-			for (int k = 0; k < s; k++) {
-				ll u = a[j + k], t = a[j + s + k];
-				if (!inverse) {
-					a[j + k] = u + t;
-					a[j + s + k] = u;
-				} else {
-					a[j + k] = t;
-					a[j + s + k] = u - t;
-}}}}}
+		for (int i = 0; i < n; i += 2 * s) {
+			for (int j = i; j < i + s; j++) {
+				ll& u = a[j], &v = a[j + s];
+				tie(u, v) = inv ? pair(v, u - v) : pair(u + v, u);
+}}}}