프로그램 명: coci_hash
제한시간: 1 초
세운이는 단어와 정수 간의 함수인 해쉬 함수를 배우고 있다. 예제로 주어진 해쉬 함수는 아래와 같이 정의되어 있다.
-
- f(빈 단어) = 0
-
- f(단어 + 문자) = ((f(단어) * 33) XOR ord(문자)) % MOD
이 함수는 오직 영어 소문자로 이루어진 단어만을 정의역으로 갖고 있다. XOR 연산은 컴퓨터에서 이루어지는 비트 연산을 의미하고 (예를 들어, 0110 XOR 1010 = 1100), ord(문자) 는 각 문자의 알파벳 순서를 의미하고 (예를 들어, ord(a)=1, ord(z)=26), A % B는 A를 B로 나눈 나머지를 의미한다. 또한, MOD는 2^M 과 같다.
M=10일 때, f(a)=1, f(aa)=32, f(kit)=438이다.
세운이는 해쉬 값이 정확히 K가 되는 길이 N의 단어가 몇 개나 되는지 알고 싶어한다. 세운이를 도와 해쉬 값이 K가 되는 단어의 개수를 구해주자.
입력 형식
-
첫 번째 줄에 단어의 길이 N, 해쉬 값 K, 비트의 수 M이 주어진다.
(1 ≤ N ≤ 10, 0 ≤ K < 2^M, 6 ≤ M ≤ 25)
전체 데이터의 30%는 N이 5 이하이다.
전체 데이터의 60%는 M이 15 이하이다.
출력 형식
해쉬 값이 K인 단어의 개수를 출력한다.
입력 예 1
1 0 10
출력 예 1
0
입력 예 2
1 2 10
출력 예 2
1
입력 예 3
3 16 10
출력 예 3
4
예제 설명
입력 예 1 설명: 해쉬 값이 0인 단어는 존재하지 않는다.
입력 예 2 설명: 해쉬 값이 2인 단어는 "b"뿐이다.
입력 예 3 설명: 해쉬 값이 16인 단어는 “dxl", "hph", "lxd", "xpx"가 있다.
Little Mirko is studying the hash function which associates numerical values to words. The function is
defined recursively in the following way:
- f( empty word ) = 0
- f( word + letter ) = ( ( f( word ) * 33 ) XOR ord( letter ) ) % MOD
The function is defined for words that consist of only lowercase letters of the English alphabet. XOR
stands for the bitwise XOR operator (i.e. 0110 XOR 1010 = 1100), ord(letter) stands for the ordinal
number of the letter in the alphabet (ord(a) = 1, ord(z) = 26) and A % B stands for the remainder of
the number A when performing integer division with the number B. MOD will be an integer of the form 2^M .
Some values of the hash function when M = 10:
- f( a ) = 1
- f ( aa ) = 32
- f ( kit ) = 438
Mirko wants to find out how many words of the length N there are with the hash value K. Write a
programme to help him calculate this number.
INPUT
The first line of input contains three integers N, K and M (1 ≤ N ≤ 10, 0 ≤ K < 2^M , 6 ≤ M ≤ 25).
OUTPUT
The first and only line of output must consist of the required number from the task.
SAMPLE TESTS
input
1 0 10
output
0
input
1 2 10
output
1
input
3 16 10
output
4
Clarification of the first example: None of the characters in the alphabet has an ord value 0.
Clarification of the second example: It is the word “b”.
Clarification of the third example: Those are the words “dxl”, “hph”, “lxd” and “xpx”.
출처:coci/2013-2014/contest6 5 번
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]