[백준] 15829 Hashing c++

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

15829번: Hashing

 

보자 마다 쉽다고 생각했는데 50 점 맞았다.

문제는 Hash값을 M으로 나누어주는 것만 생각하고 31의 거듭제곱을 나누어줄 생각을 못했다는 것이다.

#include<iostream>
#include<string>

using namespace std;

int main()
{
	int n;
	string s;
	cin >> n;
	cin >> s;
	int M = 1234567891;
	long long hash=0,j=1;
	for (int i = 0 ; i < n; i++,j*=31)
	{
		hash += ((s[i] - 'a'+1 )* (j%M));
		j %= M;
		hash %= M;
	}
	cout << hash;
}