[C++][백준 15829] Hashing

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

 

제출 코드

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

long long square(int a, int b)
{
    long long res = 1;
    for (int i = 0; i < b; i++)
        res = (res * a) % 1234567891;
    return res;
}

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

    int l;
    string str;
    cin >> l >> str;

    long long hash = 0;
    for (int i = 0; i < l; i++)
    {
        hash = (hash + ((str[i] - 'a' + 1) * square(31, i))) % 1234567891;
    }
    hash = hash % 1234567891;
    cout << hash;
}

자꾸 50점만 떠서 애먹었던 문제...

최대 31^49 * 26의 값을 담아둬야 해서 int 쓰던 걸 long long으로 바꾸고

중간중간 계산하면서 계속 나눠주었다

정확히 언제 언제 나눠도 되는지 잘 모르겠어서 모든 계산마다 나눠주었다...