BOJ 13318 위험한 해싱

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

13318번: 위험한 해싱

풀이

두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다.

• $\deg f < 300000$
• $f(x) = a_{0} + a_{1}x^{1} + \cdots + a_{d}x^{d}$에서, $-26 < a_{d} < 26$
• $f(23) = f(29) = \cdots = f(67) = 0$ $\text{mod}$ $10^{9} + 7$

하지만 다항식 하나에 10개의 영점을 강제하기는 너무 어렵다.

그래서 생각하기를 $f_{1}(23) = 0$을 만족하는 계수가 작은 다항식 $f_{1}(x)$를 찾고, 똑같이 $f_{2}(29) = 0$을 만족하는 계수가 작은 다항식 $f_{2}(x)$를 찾고, ... 그렇게 $f(x) = f_{1}(x)f_{2}(x) \cdots f_{10}(x)$로 쓰면 되지 않을까? 계수가 작은 다항식끼리 곱해서 계수가 많이 커지지는 않을 것 같다.

 

그럼 이제 $f_{i}(x)$를 잘 찾는 문제가 된다. 다항식을 10개로 쪼갰으니 평균 차수가 $30000$ 이하여야 한다. 그런데 허탈하게도 $f_{i}(x)$는 다음 형태로만 잡아줘도 충분하다.

$$f_{i}(x) = 1 \pm x^{\alpha} \pm x^{\beta}$$

 

대충 생각해 보면, $p = 10^{9} + 7$의 원시근이 많으니까 대부분 $x^{\alpha}$와 $x^{\beta}$는 다를 거고, 각각 $30000$개 정도 더하고 빼면 하나쯤 0이 나올 만하다. 이론적 근거가 있는지는 모르겠다. 있다면 제보해 주시길.

 

어쨌든 저 다항식들을 싸그리 곱해도 계수가 $\pm 5$는 넘어가지 않는 것 같다. Output only이기 때문에 충분한 디버깅을 거쳐서 기분좋게 한 방에 맞을 수 있다.