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이기 때문에 충분한 디버깅을 거쳐서 기분좋게 한 방에 맞을 수 있다.