use int128 for hash

1 files changed, 12 insertions, 17 deletions

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;}
 };