diff options
Diffstat (limited to 'math/transforms/orTransform.cpp')
| -rw-r--r-- | math/transforms/orTransform.cpp | 21 |
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); +}}}} |