diff options
Diffstat (limited to 'math/transforms/xorTransform.cpp')
| -rw-r--r-- | math/transforms/xorTransform.cpp | 21 |
1 files changed, 7 insertions, 14 deletions
diff --git a/math/transforms/xorTransform.cpp b/math/transforms/xorTransform.cpp index 48e4df2..f9d1d82 100644 --- a/math/transforms/xorTransform.cpp +++ b/math/transforms/xorTransform.cpp @@ -1,17 +1,10 @@ -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]; - a[j + k] = u + 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) = pair(u + v, u - v); }}} - if (inverse) { - for (ll i = 0; i < n; i++) { - a[i] /= n; -}}} + if (inv) for (ll& x : a) x /= n; +} |