[BOJ 26008] 해시 해킹

$h(P)=(P_0\times A^0+P_1\times A^1+\dots+P_{N-1}\times A^{N-1})\ mod\ M$ 에서 $P_0\times A^0+P_1\times A^1+\dots+P_{N-1}\times A^{N-1}$의 형태는 마치 $A$진법의 형태와 같다.

 

이러한 형태에서 $P_i\lt A_i$라면 $P_0\times A^0+P_1\times A^1+\dots+P_{N-1}\times A^{N-1}$는 고유한(중복되지 않는) 값을 가질 것이다. 하지만 이는 문제와 크게 관련이 없으니 넘어가도록 하자.

 

위의 식을 조금 정리해 보자. 

$h(P)=(P_0\times A^0+P_1\times A^1+\dots+P_{N-1}\times A^{N-1})\ mod\ M$에서 $P_0\times A^0$는 $P_0$이다. 문제에서 주어지는 $A$와 관련 없이 상수가 된다. 

 

$h(P)=(P_0+P_1\times A^1+\dots+P_{N-1}\times A^{N-1})\ mod\ M$ 에서 $P_1\times A^1+\dots+P_{N-1}\times A^{N-1}$ 부분을 $K$로 놓자.

 

$h(P)=(P_0+K)\ mod\ M$으로 정리를 할 수 있다. 

모듈러 연산에 의해 $h(P)=(P_0\ mod\ M + K\ mod\ M)\ mod\ M$으로 나타낼 수 있다.

 

$h(P)=(0\sim M-1 + 0\sim M-1)\ mod\ M$가 되므로 $K$가 어떠한 값이 되더라도 $P_0$값을 임의로 정하여 $h(P)$의 값이 $H$가 되도록 정할 수 있다. $P_0$값은 $M$ 이상이 아니므로 어느 $H$에 대해 $K$가 정해졌을 때, 단 하나의 $P_0$값만 $H$를 만들 수 있다. 

 

결국, $K$의 경우의 수를 세어주면, 그것이 $H$를 만들 수 있는 경우의 수가 되는 것이다. $M^{N-1}$을 $10^9+7$로 나눈 나머지를 출력해 주면 된다.