diff options
| author | Yidi <noob999noob999@gmail.com> | 2024-03-22 12:16:34 +0100 |
|---|---|---|
| committer | Yidi <noob999noob999@gmail.com> | 2024-03-22 12:16:34 +0100 |
| commit | f1261bb7cd35840b9b5937a6260308f3839c6f3e (patch) | |
| tree | 2042f32b7c5b4cec7255e66f32f75640ec529f11 /math | |
| parent | 9906aa7bbf98bee5cdb91e80f6a2311e43129c7d (diff) | |
minor (mostly spacing) changes
Diffstat (limited to 'math')
| -rw-r--r-- | math/binomial1.cpp | 3 | ||||
| -rw-r--r-- | math/chineseRemainder.cpp | 26 | ||||
| -rw-r--r-- | math/transforms/seriesOperations.cpp | 41 |
3 files changed, 35 insertions, 35 deletions
diff --git a/math/binomial1.cpp b/math/binomial1.cpp index 02b27e3..dab20b3 100644 --- a/math/binomial1.cpp +++ b/math/binomial1.cpp @@ -2,8 +2,7 @@ ll calc_binom(ll n, ll k) { if (k > n) return 0; ll r = 1; for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit - r *= n--; - r /= d; + r *= n--, r /= d; } return r; } diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index a1aa480..b02de48 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,14 @@ -struct CRT{ - using lll = __int128_t; - lll M = 1, sol = 0; // Solution unique modulo M - bool hasSol = true; +struct CRT { + using lll = __int128; + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - // Adds congruence x = a (mod m) - void add(ll a, ll m){ - ll s, t, d = extendedEuclid(M, m, s, t); - if((a - sol) % d != 0) hasSol = false; - lll z = M/d * s; - M *= m/d; - sol = (z % M * (a-sol) % M + sol + M) % M; - } -};
\ No newline at end of file + // Adds congruence x = a (mod m) + void add(ll a, ll m) { + auto [d, s, t] = extendedEuclid(M, m); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; + } +}; diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp index 3851a1e..4743674 100644 --- a/math/transforms/seriesOperations.cpp +++ b/math/transforms/seriesOperations.cpp @@ -1,55 +1,56 @@ -vector<ll> poly_inv(vector<ll> a, int n){ +vector<ll> poly_inv(const vector<ll>& a, int n) { vector<ll> q = {powMod(a[0], mod-2, mod)}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2){ vector<ll> a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for(int j = 0; j < 2; j++){ + for (int j : {0, 1}) { ntt(a2); - for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); - for(int i = 0; i < len; i++) a2[i] = 0; + for (int i = 0; i < len; i++) a2[i] = 0; } - for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod); - } + for (int i = len; i < min(n, 2*len); i++) { + q.push_back((mod - a2[i]) % mod); + }} return q; } -vector<ll> poly_deriv(vector<ll> a){ - for(int i = 0; i < sz(a)-1; i++) - a[i] = a[i+1] * (i+1) % mod; +vector<ll> poly_deriv(vector<ll> a) { + for (int i = 1; i < sz(a); i++) + a[i-1] = a[i] * i % mod; a.pop_back(); return a; } -vector<ll> poly_integr(vector<ll> a){ - if(a.empty()) return {0}; +vector<ll> poly_integr(vector<ll> a) { + if (a.empty()) return {0}; a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for(int i = sz(a)-2; i > 0; i--) + for (int i = sz(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; } -vector<ll> poly_log(vector<ll> a, int n){ +vector<ll> poly_log(vector<ll> a, int n) { a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); a = poly_integr(a); return a; } -vector<ll> poly_exp(vector<ll> a, int n){ +vector<ll> poly_exp(vector<ll> a, int n) { vector<ll> q = {1}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2) { vector<ll> p = poly_log(q, 2*len); - for(int i = 0; i < 2*len; i++) + for (int i = 0; i < 2*len; i++) p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); - for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; ntt(p, true); - for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); } return q; -}
\ No newline at end of file +} |
