해시 함수

시간 제한3초메모리 제한256 MB

요약

길이 N인 소문자 단어 중 33 곱셈과 xor를 반복한 해시를 2^M으로 나눈 나머지가 K인 경우를 셉니다.

난이도: 보통10점 중 7점
유형: 분할 정복, 해시맵, 완전 탐색, 정수론
정답자: 아직 제출이 없습니다

문제

창영이는 시스템 프로그래밍 숙제에 쓸 해시 함수를 만들고 있다. 이 함수는 단어를 숫자로 바꾸며, 다음과 같이 재귀적으로 정의된다.

$f(\varepsilon) = 0$
$f(w + x) = ((f(w) \times 33) \oplus \mathrm{ord}(x)) \bmod 2^M$

$\varepsilon$ 은 빈 단어, $w$ 는 단어, $x$ 는 그 뒤에 붙이는 한 글자다. 단어는 알파벳 소문자로만 이루어진다. $\oplus$ 는 비트 단위 XOR 연산이고 ( $0110 \oplus 1010 = 1100$ ), $\mathrm{ord}(x)$ 는 $x$ 가 알파벳에서 몇 번째 글자인지를 나타낸다 ( $\mathrm{ord}(a) = 1$ , $\mathrm{ord}(z) = 26$ ). $A \bmod B$ 는 $A$ 를 $B$ 로 나눈 나머지다.

$M = 10$ 이면 해시값은 다음과 같다.

$f(a) = 1$
$f(aa) = 32$
$f(kit) = 438$

길이가 $N$ 인 단어 중 해시값이 $K$ 인 것이 몇 개인지 세는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ , $K$ , $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N \le 10$ , $0 \le K < 2^M$ , $6 \le M \le 25$ )

출력

길이가 $N$ 이고 해시값이 $K$ 인 단어의 개수를 출력한다.

힌트

$N = 3$ , $K = 16$ , $M = 10$ 일 때 조건을 만족하는 단어는 dxl, hph, lxd, xpx이다.

예제3

예제 1
입력
```
1 0 10
```
예상 출력
```
0
```
예제 2
입력
```
1 2 10
```
예상 출력
```
1
```
예제 3
입력
```
3 16 10
```
예상 출력
```
4
```