diff options
| -rw-r--r-- | datastructures/segmentTree.cpp | 2 | ||||
| -rw-r--r-- | string/rollingHash2.cpp | 29 |
2 files changed, 13 insertions, 18 deletions
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 5a75d69..79c6cae 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -11,7 +11,7 @@ struct SegTree { tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - ll comb(T a, T b) { return a + b; } // modify this + neutral + ll comb(T a, T b) {return a + b;} // modify this + neutral void update(int i, T val) { tree[i += n] = val; // apply update code diff --git a/string/rollingHash2.cpp b/string/rollingHash2.cpp index 7660842..f60db2e 100644 --- a/string/rollingHash2.cpp +++ b/string/rollingHash2.cpp @@ -1,23 +1,18 @@ // M = 1.7e9 + 9, 1e18L + 9, 2.2e18L + 7 struct Hash { - static constexpr ll M = 3.1e18L + 7; - static constexpr ll Q = 2e18L + 43; // Random number in [SIGMA+1, M) - vector<ll> pref = {0}, power = {1}; + static constexpr ll M = 3e18L + 37; + static constexpr ll Q = 318LL << 53; // Random in [SIGMA+1, M) + vector<ll> pref = {0}, power = {1}; - Hash(const string& s) { - for (auto c : s) { - pref.push_back((mul(pref.back(), Q) + c) % M); - power.push_back(mul(power.back(), Q)); - }} + Hash(const string& s) { + for (auto c : s) { + pref.push_back((mul(pref.back(), Q) + c + M) % M); + power.push_back(mul(power.back(), Q)); + }} - ll operator()(int l, int r) { - return (pref[r] - mul(power[r-l], pref[l]) + M) % M; - } + ll operator()(int l, int r) { + return (pref[r] - mul(power[r-l], pref[l]) + M) % M; + } - // can also just use __int128 multiplication and mod (slower) - using ull = uint64_t; - static ll mul(ull a, ull b) { // 0 < a,b <= M <= 7.268 * 10^18 - ll ans = (a * b - M * ull(1.L / M * a * b)); - return ans + M * ((ans < 0) - (ans >= M)); - } + static ll mul(__int128 a, ll b) {return a * b % M;} }; |