summaryrefslogtreecommitdiff
path: root/math/transforms
diff options
context:
space:
mode:
Diffstat (limited to 'math/transforms')
-rw-r--r--math/transforms/all.cpp62
-rw-r--r--math/transforms/andTransform.cpp17
-rw-r--r--math/transforms/fft.cpp20
-rw-r--r--math/transforms/fftMul.cpp14
-rw-r--r--math/transforms/fftPerm.cpp8
-rw-r--r--math/transforms/ntt.cpp28
-rw-r--r--math/transforms/orTransform.cpp17
-rw-r--r--math/transforms/xorTransform.cpp17
8 files changed, 183 insertions, 0 deletions
diff --git a/math/transforms/all.cpp b/math/transforms/all.cpp
new file mode 100644
index 0000000..4f4d83b
--- /dev/null
+++ b/math/transforms/all.cpp
@@ -0,0 +1,62 @@
+/*constexpr ll mod = 998244353; @\hl{NTT only}@
+constexpr ll root = 3;*/
+
+using cplx = complex<double>;
+
+@\hl{NTT, xor, or, and}@
+//void fft(vector<ll> &a, bool inverse = 0) {
+void fft(vector<cplx>& a, bool inverse = 0) {
+ int n = a.size();
+ 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) {
+ /*ll ws = powMod(root, (mod - 1) / s >> 1, mod); @\hl{NTT only}@
+ if (inverse) ws = powMod(ws, mod - 2, mod);*/
+ double angle = PI / s * (inverse ? -1 : 1);
+ cplx ws(cos(angle), sin(angle));
+ for (int j = 0; j < n; j+= 2 * s) {
+ //ll w = 1; @\hl{NTT only}@
+ cplx w = 1;
+ for (int k = 0; k < s; k++) {
+ /*ll u = a[j + k], t = a[j + s + k] * w; @\hl{NTT only}@
+ t %= mod;
+ a[j + k] = (u + t) % mod;
+ a[j + s + k] = (u - t + mod) % mod;
+ w *= ws;
+ w %= mod;*/
+ /*ll u = a[j + k], t = a[j + s + k]; @\hl{xor only}@
+ a[j + k] = u + t;
+ a[j + s + k] = u - t;*/
+ /*if (!inverse) { @\hl{or only}@
+ a[j + k] = u + t;
+ a[j + s + k] = u;
+ } else {
+ a[j + k] = t;
+ a[j + s + k] = u - t;
+ }*/
+ /*if (!inverse) { @\hl{and only}@
+ a[j + k] = t;
+ a[j + s + k] = u + t;
+ } else {
+ a[j + k] = t - u;
+ a[j + s + k] = u;
+ }*/
+ cplx u = a[j + k], t = a[j + s + k] * w;
+ a[j + k] = u + t;
+ a[j + s + k] = u - t;
+ if (inverse) a[j + k] /= 2, a[j + s + k] /= 2;
+ w *= ws;
+ }}}
+ /*if (inverse) { @\hl{NTT only}@
+ ll div = powMod(n, mod - 2, mod);
+ for (ll i = 0; i < n; i++) {
+ a[i] *= div;
+ a[i] %= mod;
+ }}*/
+ /*if (inverse) { @\hl{xor only}@
+ for (ll i = 0; i < n; i++) {
+ a[i] /= n;
+ }}*/
+}
diff --git a/math/transforms/andTransform.cpp b/math/transforms/andTransform.cpp
new file mode 100644
index 0000000..cdc7b22
--- /dev/null
+++ b/math/transforms/andTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<cplx>& a, bool inverse = 0) {
+ 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;
+}}}} \ No newline at end of file
diff --git a/math/transforms/fft.cpp b/math/transforms/fft.cpp
new file mode 100644
index 0000000..4540ed8
--- /dev/null
+++ b/math/transforms/fft.cpp
@@ -0,0 +1,20 @@
+using cplx = complex<double>; // Eigene Implementierung ist schneller.
+
+void fft(vector<cplx>& a, bool inverse = 0) {
+ 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) {
+ double angle = PI / s * (inverse ? -1 : 1);
+ cplx ws(cos(angle), sin(angle));
+ for (int j = 0; j < n; j+= 2 * s) {
+ cplx w = 1;
+ for (int k = 0; k < s; k++) {
+ cplx u = a[j + k], t = a[j + s + k] * w;
+ a[j + k] = u + t;
+ a[j + s + k] = u - t;
+ if (inverse) a[j + k] /= 2, a[j + s + k] /= 2;
+ w *= ws;
+}}}}
diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp
new file mode 100644
index 0000000..dc19412
--- /dev/null
+++ b/math/transforms/fftMul.cpp
@@ -0,0 +1,14 @@
+vector<cplx> mul(vector<cplx>& a, vector<cplx>& b) {
+ vector<cplx> c(a.size()), d(a.size());
+ for (int i = 0; i < b.size(); i++) {
+ c[i] = {real(a[i]), real(b[i])};
+ }
+ c = fft(c);
+ for (int i = 0; i < b.size(); i++) {
+ int j = (a.size() - i) % a.size();
+ cplx x = (c[i] + conj(c[j])) / cplx{2, 0}; //fft(a)[i];
+ cplx y = (c[i] - conj(c[j])) / cplx{0, 2}; //fft(b)[i];
+ d[i] = x * y;
+ }
+ return fft(d, true);
+}
diff --git a/math/transforms/fftPerm.cpp b/math/transforms/fftPerm.cpp
new file mode 100644
index 0000000..2b6fb10
--- /dev/null
+++ b/math/transforms/fftPerm.cpp
@@ -0,0 +1,8 @@
+int perm[MAXN]; //perm[i] = j in Zeile 10
+void genPerm(int n){
+ ull mask = ~0ull << (__lg(n) - 1);
+ for (int i = 0, j = 0; i < n; i++) {
+ perm[i] = j; //if (i < j) swap(a[i], a[j]);
+ ull y = mask >> __builtin_ctz(~i);
+ j ^= y & (n - 1);
+}}
diff --git a/math/transforms/ntt.cpp b/math/transforms/ntt.cpp
new file mode 100644
index 0000000..e1e4588
--- /dev/null
+++ b/math/transforms/ntt.cpp
@@ -0,0 +1,28 @@
+constexpr ll mod = 998244353;
+constexpr ll root = 3;
+
+void fft(vector<ll>& a, bool inverse = 0) {
+ 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) {
+ ll ws = powMod(root, (mod - 1) / s >> 1, mod);
+ if (inverse) ws = powMod(ws, mod - 2, mod);
+ for (int j = 0; j < n; j+= 2 * s) {
+ ll w = 1;
+ for (int k = 0; k < s; k++) {
+ ll u = a[j + k], t = a[j + s + k] * w;
+ t %= mod;
+ a[j + k] = (u + t) % mod;
+ a[j + s + k] = (u - t + mod) % mod;
+ w *= ws;
+ w %= mod;
+ }}}
+ if (inverse) {
+ ll div = powMod(n, mod - 2, mod);
+ for (ll i = 0; i < n; i++) {
+ a[i] *= div;
+ a[i] %= mod;
+}}}
diff --git a/math/transforms/orTransform.cpp b/math/transforms/orTransform.cpp
new file mode 100644
index 0000000..fdb5bb8
--- /dev/null
+++ b/math/transforms/orTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<ll>& a, bool inverse = 0) {
+ 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;
+}}}}}
diff --git a/math/transforms/xorTransform.cpp b/math/transforms/xorTransform.cpp
new file mode 100644
index 0000000..48e4df2
--- /dev/null
+++ b/math/transforms/xorTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<ll>& a, bool inverse = 0) {
+ 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];
+ a[j + k] = u + t;
+ a[j + s + k] = u - t;
+ }}}
+ if (inverse) {
+ for (ll i = 0; i < n; i++) {
+ a[i] /= n;
+}}}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:24:21 +0000