Hash
레이팅 미적용의견: 0
\(6^{th}\) round, March \(8^{th}\), 2014
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( wo\(rd + le\)tter ) = ( ( 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.
In test cases worth 30% of total points, N will not exceed 5.
Additionally, in test cases worth 60% of total points, M will not exceed 15.
The first line of input contains three integers N, K and M (\(1 \le N \le 10\), \(0 \le K < 2^{M}\), \(6 \le M \le 25\)).
The first and only line of output must consist of the required number from the task.
1 0 1001 2 1013 16 104Clarification 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”.
평가 및 의견
Hash
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Hash