summaryrefslogtreecommitdiff
path: root/content/math/transforms
diff options
context:
space:
mode:
Diffstat (limited to 'content/math/transforms')
-rw-r--r--content/math/transforms/andTransform.cpp6
-rw-r--r--content/math/transforms/bitwiseTransforms.cpp8
-rw-r--r--content/math/transforms/fft.cpp2
-rw-r--r--content/math/transforms/fftMul.cpp6
-rw-r--r--content/math/transforms/multiplyBitwise.cpp2
-rw-r--r--content/math/transforms/multiplyFFT.cpp4
-rw-r--r--content/math/transforms/multiplyNTT.cpp2
-rw-r--r--content/math/transforms/ntt.cpp2
-rw-r--r--content/math/transforms/orTransform.cpp6
-rw-r--r--content/math/transforms/seriesOperations.cpp8
-rw-r--r--content/math/transforms/xorTransform.cpp4
11 files changed, 25 insertions, 25 deletions
diff --git a/content/math/transforms/andTransform.cpp b/content/math/transforms/andTransform.cpp
index 1fd9f5c..87bae0b 100644
--- a/content/math/transforms/andTransform.cpp
+++ b/content/math/transforms/andTransform.cpp
@@ -1,8 +1,8 @@
void fft(vector<ll>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(a);
for (int s = 1; s < n; s *= 2) {
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);
+ ll &u = a[j], &v = a[j + s];
+ u = inv ? u - v : u + v;
}}}}
diff --git a/content/math/transforms/bitwiseTransforms.cpp b/content/math/transforms/bitwiseTransforms.cpp
index 28561da..c0f6e50 100644
--- a/content/math/transforms/bitwiseTransforms.cpp
+++ b/content/math/transforms/bitwiseTransforms.cpp
@@ -1,11 +1,11 @@
void bitwiseConv(vector<ll>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(a);
for (int s = 1; s < n; s *= 2) {
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); // AND
- //tie(u, v) = inv ? pair(v, u - v) : pair(u + v, u); //OR
+ ll &u = a[j], &v = a[j + s];
+ u = inv ? u - v : u + v; // AND
+ //v = inv ? v - u : v + u; // OR
//tie(u, v) = pair(u + v, u - v); // XOR
}}}
//if (inv) for (ll& x : a) x /= n; // XOR (careful with MOD)
diff --git a/content/math/transforms/fft.cpp b/content/math/transforms/fft.cpp
index 2bd95b2..1f80e36 100644
--- a/content/math/transforms/fft.cpp
+++ b/content/math/transforms/fft.cpp
@@ -1,7 +1,7 @@
using cplx = complex<double>;
void fft(vector<cplx>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(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]);
diff --git a/content/math/transforms/fftMul.cpp b/content/math/transforms/fftMul.cpp
index 660ed79..da6a538 100644
--- a/content/math/transforms/fftMul.cpp
+++ b/content/math/transforms/fftMul.cpp
@@ -1,8 +1,8 @@
vector<cplx> mul(vector<ll>& a, vector<ll>& b) {
- int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1);
- vector<cplx> c(all(a)), d(n);
+ int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1);
+ vector<cplx> c(begin(a), end(a)), d(n);
c.resize(n);
- for (int i = 0; i < sz(b); i++) c[i] = {real(c[i]), b[i]};
+ for (int i = 0; i < ssize(b); i++) c[i] = {real(c[i]), b[i]};
fft(c);
for (int i = 0; i < n; i++) {
int j = (n - i) & (n - 1);
diff --git a/content/math/transforms/multiplyBitwise.cpp b/content/math/transforms/multiplyBitwise.cpp
index f7cf169..5275b8c 100644
--- a/content/math/transforms/multiplyBitwise.cpp
+++ b/content/math/transforms/multiplyBitwise.cpp
@@ -1,5 +1,5 @@
vector<ll> mul(vector<ll> a, vector<ll> b) {
- int n = 1 << (__lg(2 * max(sz(a), sz(b)) - 1));
+ int n = 1 << (__lg(2 * max(ssize(a), ssize(b)) - 1));
a.resize(n), b.resize(n);
bitwiseConv(a), bitwiseConv(b);
for (int i=0; i<n; i++) a[i] *= b[i]; // MOD?
diff --git a/content/math/transforms/multiplyFFT.cpp b/content/math/transforms/multiplyFFT.cpp
index 0022d1f..963be94 100644
--- a/content/math/transforms/multiplyFFT.cpp
+++ b/content/math/transforms/multiplyFFT.cpp
@@ -1,6 +1,6 @@
vector<ll> mul(vector<ll>& a, vector<ll>& b) {
- int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1);
- vector<cplx> a2(all(a)), b2(all(b));
+ int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1);
+ vector<cplx> a2(begin(a), end(a)), b2(begin(b), end(b));
a2.resize(n), b2.resize(n);
fft(a2), fft(b2);
for (int i=0; i<n; i++) a2[i] *= b2[i];
diff --git a/content/math/transforms/multiplyNTT.cpp b/content/math/transforms/multiplyNTT.cpp
index 806d124..d234ce3 100644
--- a/content/math/transforms/multiplyNTT.cpp
+++ b/content/math/transforms/multiplyNTT.cpp
@@ -1,5 +1,5 @@
vector<ll> mul(vector<ll> a, vector<ll> b) {
- int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1);
+ int n = 1 << bit_width(size(a) + size(b) - 1);
a.resize(n), b.resize(n);
ntt(a), ntt(b);
for (int i=0; i<n; i++) a[i] = a[i] * b[i] % mod;
diff --git a/content/math/transforms/ntt.cpp b/content/math/transforms/ntt.cpp
index ca605d3..fc7874e 100644
--- a/content/math/transforms/ntt.cpp
+++ b/content/math/transforms/ntt.cpp
@@ -1,7 +1,7 @@
constexpr ll mod = 998244353, root = 3;
void ntt(vector<ll>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(a);
auto b = a;
ll r = inv ? powMod(root, mod - 2, mod) : root;
diff --git a/content/math/transforms/orTransform.cpp b/content/math/transforms/orTransform.cpp
index eb1da44..1833ac5 100644
--- a/content/math/transforms/orTransform.cpp
+++ b/content/math/transforms/orTransform.cpp
@@ -1,8 +1,8 @@
void fft(vector<ll>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(a);
for (int s = 1; s < n; s *= 2) {
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);
+ ll &u = a[j], &v = a[j + s];
+ v = inv ? v - u : v + u;
}}}}
diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp
index b405698..3d8aa11 100644
--- a/content/math/transforms/seriesOperations.cpp
+++ b/content/math/transforms/seriesOperations.cpp
@@ -17,7 +17,7 @@ vector<ll> poly_inv(const vector<ll>& a, int n) {
}
vector<ll> poly_deriv(vector<ll> a) {
- for (int i = 1; i < sz(a); i++)
+ for (int i = 1; i < ssize(a); i++)
a[i-1] = a[i] * i % mod;
a.pop_back();
return a;
@@ -25,11 +25,11 @@ vector<ll> poly_deriv(vector<ll> a) {
vector<ll> poly_integr(vector<ll> a) {
static vector<ll> inv = {0, 1};
- for (static int i = 2; i <= sz(a); i++)
+ for (static int i = 2; i <= ssize(a); i++)
inv.push_back(mod - mod / i * inv[mod % i] % mod);
a.push_back(0);
- for (int i = sz(a) - 1; i > 0; i--)
+ for (int i = ssize(a) - 1; i > 0; i--)
a[i] = a[i-1] * inv[i] % mod;
a[0] = 0;
return a;
@@ -46,7 +46,7 @@ vector<ll> poly_exp(vector<ll> a, int n) {
for (int len = 1; len < n; len *= 2) {
vector<ll> p = poly_log(q, 2*len);
for (int i = 0; i < 2*len; i++)
- p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod;
+ p[i] = (mod - p[i] + (i < ssize(a) ? a[i] : 0)) % mod;
vector<ll> q2 = q;
q2.resize(2*len);
ntt(p), ntt(q2);
diff --git a/content/math/transforms/xorTransform.cpp b/content/math/transforms/xorTransform.cpp
index f9d1d82..aa3db8d 100644
--- a/content/math/transforms/xorTransform.cpp
+++ b/content/math/transforms/xorTransform.cpp
@@ -1,9 +1,9 @@
void fft(vector<ll>& a, bool inv = false) {
- int n = sz(a);
+ int n = ssize(a);
for (int s = 1; s < n; s *= 2) {
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];
+ ll &u = a[j], &v = a[j + s];
tie(u, v) = pair(u + v, u - v);
}}}
if (inv) for (ll& x : a) x /= n;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:06:08 +0000