15829번: Hashing
접근 방법
모듈로 연산의 성질을 이용하여 매 연산마다 모듈로를 취해 계산해줍니다.
모듈로 연산은 나눗셈을 제외한 연산에 대해 다음과 같은 특성을 가집니다.
$(a + b)\mod n = (a \mod n + b \mod n) \mod n$
$(a - b)\mod n = (a \mod n - b \mod n) \mod n$
$(a * b)\mod n = (a \mod n * b \mod n) \mod n$
1
2
3
| (A + B) % M = ((A % M) + (B % M)) % M
(A * B) % M = ((A % M) * (B % M)) % M
(A - B) % M = ((A % M) - (B % M)) % M
|
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
#define endl '\\n'
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define SUBMIT
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef SUBMIT
(void)!freopen("input.txt", "r", stdin);
cout << "# From the test case" << endl;
#endif
int M = 1234567891;
int r = 31;
int l;
string s;
cin >> l >> s;
ll base = 1;
ll ans = 0;
for(int i = 0; i < l; ++i) {
int num = s[i]-'a' + 1;
ans = (ans % M + ((num % M) * (base % M)) % M) % M;
base = ((base % M) * (r % M)) % M;
}
cout << ans;
return 0;
}
|