시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 112 17 14 21.875%

문제

창영이는 시스템 프로그래밍 숙제에 사용할 Hash 함수를 만들고 있다. 이 함수는 단어를 숫자로 바꾸는 Hash함수이고, 아래와 같이 재귀적으로 정의된다.

  • f(empty word) = 0
  • f(word + letter) = ((f(word) * 33) XOR ord(letter)) % MOD

단어는 알파벳 소문자로만 이루어져 있어야 한다. XOR은 XOR 연산을 나타내며 (0110 XOR 1010 = 1100), ord(letter)는 알파벳의 순서를 나타낸다. (ord(a) = 1, ord(z) = 26) A % B는 A를 B로 나눈 나머지를 나타내며, MOD는 2M이다.

M = 10인 경우에 Hash값은 아래와 같다.

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

창영이는 길이가 N인 단어 중에서 Hash값이 K인 단어의 개수를 찾으려고 한다. 이러한 단어의 개수를 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N, K, M이 주어진다. (1 ≤ N ≤ 10, 0 ≤ K < 2M, 6 ≤ M ≤ 25)

출력

길이가 N이면서 Hash값이 K인 단어의 개수를 출력한다.

예제 입력

3 16 10

예제 출력

4

힌트

가능한 단어로는 “dxl”, “hph”, “lxd”, “xpx” 가 있다.

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #6 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: wdh2100