// M = 1.7e9 + 9, 1e18L + 9, 2.2e18L + 7 struct Hash { 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) { // 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;} };

summary refs log tree commit diff

path: root/math/modPowIterativ.cpp

blob: 0dc3fb145b87f766238b7d7ddd3ba5934e395d18 (plain)

ll powMod(ll a, ll b, ll n) {
	ll res = 1;
	while (b > 0) {
		if (b & 1) res = (a * res) % n;
		a = (a * a) % n;
		b /= 2;
	}
	return res;
}