[BOJ]15829-Hashing

15829

문자열이 너무 커져서 방법을 찾아보다가 계산기로 연산 하나하나 쪼개서 연습해봤다. 곱하고 더하는 각 연산 사이에 모듈러 연산을 해도 값이 똑같이 나왔다.
해싱은 알다가도 모르겠당

성공코드

#include <iostream>
#include <string>
using namespace std;

const int r = 31;
const long long m = 1234567891;

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int N;

	cin >> N;

	string str;

	cin >> str;

	long long  total = 0;


	for (int i = 0; i < N; i++)
	{
		long long num = str[i] - 'a' + 1;

		for (int j = 0; j < i; j++)
		{
			num *= r;
			num %= m;
		}

		total += num;
	}

	while (total >= m)
	{
		total %= m;
	}

	
	cout << total;

}