시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB260493822.093%

문제

창영이는 시스템 프로그래밍 숙제에 사용할 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인 단어의 개수를 출력한다.

예제 입력 1

1 0 10

예제 출력 1

0

예제 입력 2

1 2 10

예제 출력 2

1

예제 입력 3

3 16 10

예제 출력 3

4

힌트

예제 3의 경우 가능한 단어로는 “dxl”, “hph”, “lxd”, “xpx” 가 있다.

W3sicHJvYmxlbV9pZCI6IjEwMDAxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSGFzaCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzJkY1x1YzJhNFx1ZDE1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjMjE5XHVjODFjXHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBIYXNoIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTY4XHVjMjE4XHViMjk0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWMyMmJcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IEhhc2ggXHVkNTY4XHVjMjE4XHVjNzc0XHVhY2UwLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzdhY1x1YWRjMFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+ZihlbXB0eSB3b3JkKSA9IDA8XC9saT5cclxuXHQ8bGk+Zih3b3JkICsgbGV0dGVyKSA9ICgoZih3b3JkKSAqIDMzKSBYT1Igb3JkKGxldHRlcikpICUgTU9EPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViMmU4XHVjNWI0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFhPUlx1Yzc0MCBYT1IgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCAoMDExMCBYT1IgMTAxMCA9IDExMDApLCBvcmQobGV0dGVyKVx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKG9yZChhKSA9IDEsIG9yZCh6KSA9IDI2KSBBICUgQlx1YjI5NCBBXHViOTdjIEJcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIE1PRFx1YjI5NCAyPHN1cD5NPFwvc3VwPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TSA9IDEwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBIYXNoXHVhYzEyXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+ZihhKSA9IDE8XC9saT5cclxuXHQ8bGk+ZihhYSkgPSAzMjxcL2xpPlxyXG5cdDxsaT5mKGtpdCkgPSA0Mzg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHViMmU4XHVjNWI0IFx1YzkxMVx1YzVkMFx1YzExYyBIYXNoXHVhYzEyXHVjNzc0IEtcdWM3NzggXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWM1NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4sIEssIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMCwgMCAmbGU7IEsgJmx0OyAyPHN1cD5NPFwvc3VwPiwgNiAmbGU7IE0gJmxlOyAyNSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3NFx1YmE3NFx1YzExYyBIYXNoXHVhYzEyXHVjNzc0IEtcdWM3NzggXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyAzXHVjNzU4IFx1YWNiZFx1YzZiMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmU4XHVjNWI0XHViODVjXHViMjk0ICZsZHF1bztkeGwmcmRxdW87LCAmbGRxdW87aHBoJnJkcXVvOywgJmxkcXVvO2x4ZCZyZHF1bzssICZsZHF1bzt4cHgmcmRxdW87IFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDAwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhBU0giLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBNaXJrbyBpcyBzdHVkeWluZyB0aGUgaGFzaCBmdW5jdGlvbiB3aGljaCBhc3NvY2lhdGVzIG51bWVyaWNhbCB2YWx1ZXMgdG8gd29yZHMuIFRoZSBmdW5jdGlvbiBpcyBkZWZpbmVkIHJlY3Vyc2l2ZWx5IGluIHRoZSBmb2xsb3dpbmcgd2F5OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmYoIGVtcHR5IHdvcmQgKSA9IDAmbmJzcDs8XC9saT5cclxuXHQ8bGk+Ziggd29yZCArIGxldHRlciApID0gKCAoIGYoIHdvcmQgKSAqIDMzICkgWE9SIG9yZCggbGV0dGVyICkgKSAlIE1PRCZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBmdW5jdGlvbiBpcyBkZWZpbmVkIGZvciB3b3JkcyB0aGF0IGNvbnNpc3Qgb2Ygb25seSBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gWE9SIHN0YW5kcyBmb3IgdGhlIGJpdHdpc2UgWE9SIG9wZXJhdG9yIChpLmUuIDAxMTAgWE9SIDEwMTAgPSAxMTAwKSwgb3JkKGxldHRlcikgc3RhbmRzIGZvciB0aGUgb3JkaW5hbCBudW1iZXIgb2YgdGhlIGxldHRlciBpbiB0aGUgYWxwaGFiZXQgKG9yZChhKSA9IDEsIG9yZCh6KSA9IDI2KSBhbmQgQSAlIEIgc3RhbmRzIGZvciB0aGUgcmVtYWluZGVyIG9mIHRoZSBudW1iZXIgQSB3aGVuIHBlcmZvcm1pbmcgaW50ZWdlciBkaXZpc2lvbiB3aXRoIHRoZSBudW1iZXIgQi4gTU9EIHdpbGwgYmUgYW4gaW50ZWdlciBvZiB0aGUgZm9ybSAyPHN1cD5NPFwvc3VwPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U29tZSB2YWx1ZXMgb2YgdGhlIGhhc2ggZnVuY3Rpb24gd2hlbiBNID0gMTA6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+ZiggYSApID0gMSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5mICggYWEgKSA9IDMyJm5ic3A7PFwvbGk+XHJcblx0PGxpPmYgKCBraXQgKSA9IDQzOCZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk1pcmtvIHdhbnRzIHRvIGZpbmQgb3V0IGhvdyBtYW55IHdvcmRzIG9mIHRoZSBsZW5ndGggTiB0aGVyZSBhcmUgd2l0aCB0aGUgaGFzaCB2YWx1ZSBLLiBXcml0ZSBhIHByb2dyYW1tZSB0byBoZWxwIGhpbSBjYWxjdWxhdGUgdGhpcyBudW1iZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBOLCBLIGFuZCBNICgxICZsZTsgTiAmbGU7IDEwLCAwICZsZTsgSyAmbHQ7IDI8c3VwPk08XC9zdXA+LCA2ICZsZTsgTSAmbGU7IDI1KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb25zaXN0IG9mIHRoZSByZXF1aXJlZCBudW1iZXIgZnJvbSB0aGUgdGFzay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogTm9uZSBvZiB0aGUgY2hhcmFjdGVycyBpbiB0aGUgYWxwaGFiZXQgaGFzIGFuIG9yZCB2YWx1ZSAwLjxcL3A+XHJcblxyXG48cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBzZWNvbmQgZXhhbXBsZTogSXQgaXMgdGhlIHdvcmQgJmxkcXVvO2ImcmRxdW87LjxcL3A+XHJcblxyXG48cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSB0aGlyZCBleGFtcGxlOiBUaG9zZSBhcmUgdGhlIHdvcmRzICZsZHF1bztkeGwmcmRxdW87LCAmbGRxdW87aHBoJnJkcXVvOywgJmxkcXVvO2x4ZCZyZHF1bzsgYW5kICZsZHF1bzt4cHgmcmRxdW87LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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