백준 15829 - Hashing

해시 함수를 구현하는 문제입니다. 문제에 주어진 수식을 그대로 코드로 구현하면 되는 문제입니다.

문제는 숫자가 너무 커질 경우 연산이 불가능해집니다. 이 때 모듈러 산술(Modular arithmetic) 특징 중 분배법칙을 활용해 해결할 수 있습니다.

해당 문제의 해시 함수는 다음과 같이 생겼습니다.

이걸 풀어쓰면 다음과 같습니다.

먼저 모듈러 산술 덧셈 분배법칙이 활용됩니다.

해당 식에서 0번 연산식만 떼어서 보겠습니다.

여기에서 모듈러 산술 곱셈 분배법칙이 활용됩니다.

위 연산이 $l-1$번 반복되는 형태라면 모듈려 연산으로 인해 표현 가능 숫자 범위를 넘어가지 않게 됩니다.

#include <iostream>
#include <cmath>

int main()
{
	const int r = 31;
	const int M = 1234567891;

	int l;
	std::string str;

	std::cin >> l >> str;

	long hash = 0;
	long curR = 1;

	for (int i = 0; i < l; i++)
	{
		int c = ((int)str[i] - 96); // M을 넘을 일이 없어서 M으로 나머지 연산 필요없음
		hash += c * curR % M;
		curR = (curR * r) % M;
	}

	std::cout << hash % M;

	return 0;
}