[백준 15829번] [Mod] Hashing

문제는 되게 쉬운 편이고, 시키는 대로 계산하기만 하면 되는데 Large의 경우에는 매우 숫자가 기하급수적으로 커지므로 pow함수를 이용하여 한번에 계산하기 보다는 그때그때 나머지를 연산하여 최대한 숫자를 줄이면서 계산해야 한다.

 

이 점만 유의하면 매우 쉬운 문제이다.

 

위의 내용을 바탕으로 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;
typedef long long ll;

int main(void){
    int n;
    cin >> n;
    
    string data;
    cin >> data;

    int r = 31;
    int M = 1234567891;

    ll hash = 0; 

    for(int i = 0; i < n; i++){
        int temp = data[i] - 'a' + 1;
        ll save = temp;
        for(int j = 1 ; j <= i; j++){
            save *= r;
            save %= M;
        }
        hash += save;
    }

    cout << hash % M << "\n";
    return 0;
}