[BOJ] 15829 Hashing (modulo)

https://www.acmicpc.net/problem/15829

15829번: Hashing

50점에서 화났다...

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int MOD = 1234567891;
long long R = 1;

int main() {
	int n;
	long long hash_value = 0;
	cin >>n;

	string word;
	cin >> word;

	for(int i=0; i<n; i++) {
		hash_value = (hash_value + (word[i] - 'a' + 1) * R) % MOD;

		R = (R*31) % MOD;
	}

	cout << hash_value <<endl;
}

[해결방법]

모듈로 연산의 성질을 사용한다.

(A+B) % C == (A%C + B%C) % C

(A-B) % C == (A%C - B%C) % C

(A*B) % C == (A%C * B%C) % C

 

31^50 은 long long 의 범위를 벗어나기 때문에, 모듈로 성질을 사용하자!

R = (R * 31) % 1234567891;

hash_value += ((num * R) %1234567891);