change fft, ntt and bitwise transforms

1 files changed, 6 insertions, 15 deletions

diff --git a/math/transforms/andTransform.cpp b/math/transforms/andTransform.cpp
index ab2bd40..1fd9f5c 100644
--- a/math/transforms/andTransform.cpp
+++ b/math/transforms/andTransform.cpp
@@ -1,17 +1,8 @@
-void fft(vector<cplx>& 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] = t;
-					a[j + s + k] = u + t;
-				} else {
-					a[j + k] = t - u;
-					a[j + s + k] = u;
-}}}}}
+		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, u) : pair(v, u + v);
+}}}}