blob: 84b2e4e3a0e0deb4f483b55c8852e553f1a7e262 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// M = 1.7e9 + 9, 1e18L + 9, 2.2e18L + 7
struct Hash {
static constexpr ll M = 3e18L + 37;
vector<ll> pref = {0}, power = {1};
Hash(const string& s, ll Q) { // Q Random in [SIGMA+1, M)
for (auto c : s) { // c > 0
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;
}
static ll mul(__int128 a, ll b) {return a * b % M;}
};
|
