15829 : Hashing

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int L=sc.nextInt();
		String input=sc.next();
		
		long sum=0;
		long r=1;
		for(int i=0;i<L;i++)
		{
			char c=input.charAt(i);
			
			sum+=(c-96)*r%1234567891;
			r=(r*31)%1234567891;
		}
		System.out.println(sum%1234567891);
	}
}

Class 2를 통과하기 위해서 제일 난이도 낮은 문제인 Hashing에 도전했다.

이문제가 제일 낮은 건 아니지만 내가 안 푼 것중에 제일 낮았다.

와 근데 이 문제는 서브태스크 하나는 통과하기 굉장히 쉬웠지만, 50정도 되는 큰 수를 통과하느라 애먹었다.

처음에는 BigInteger를 사용해서 큰수를 접근하는가 싶었는데, 이것도 아니고....

(그래서 구글링을 좀 했다..)

모듈러 연산을 사용하는 방법을 써야했다.

큰 수가 나오므로 큰 수를 줄여주는 나머지 연산을 이용해서 풀어야했다.

※핵심은 모듈러연산이다

문제에 나오는 (문자 mod 1234567891)*((r^31) mod 1234567891) mod 1234567891이 해법이다.

왜 마지막까지 잔실수해서 sum%1234567891을 안해서 2번인가 틀렸을까...