From 6adc67a45b665016b75b2a0958b1aa424daf2d10 Mon Sep 17 00:00:00 2001 From: Noobie99 Date: Tue, 30 Jan 2024 19:11:26 +0100 Subject: use int128 for hash --- string/rollingHash2.cpp | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) (limited to 'string/rollingHash2.cpp') 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 pref = {0}, power = {1}; + static constexpr ll M = 3e18L + 37; + static constexpr ll Q = 318LL << 53; // Random in [SIGMA+1, M) + vector 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;} }; -- cgit v1.2.3