시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 185 33 26 21.138%

문제

창영이는 시스템 프로그래밍 숙제에 사용할 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

3 16 10

예제 출력 1

4

힌트

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

W3sicHJvYmxlbV9pZCI6IjEwMDAxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSGFzaCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzJkY1x1YzJhNFx1ZDE1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjMjE5XHVjODFjXHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBIYXNoIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTY4XHVjMjE4XHViMjk0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWMyMmJcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IEhhc2hcdWQ1NjhcdWMyMThcdWM3NzRcdWFjZTAsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mKGVtcHR5IHdvcmQpID0gMDxcL2xpPlxyXG5cdDxsaT5mKHdvcmQgKyBsZXR0ZXIpID0gKChmKHdvcmQpICogMzMpIFhPUiBvcmQobGV0dGVyKSkgJSBNT0Q8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gWE9SXHVjNzQwIFhPUiBcdWM1ZjBcdWMwYjBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwICgwMTEwIFhPUiAxMDEwID0gMTEwMCksIG9yZChsZXR0ZXIpXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAob3JkKGEpID0gMSwgb3JkKHopID0gMjYpIEEgJSBCXHViMjk0IEFcdWI5N2MgQlx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgTU9EXHViMjk0IDI8c3VwPk08XC9zdXA+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5NID0gMTBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIEhhc2hcdWFjMTJcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mKGEpID0gMTxcL2xpPlxyXG5cdDxsaT5mKGFhKSA9IDMyPFwvbGk+XHJcblx0PGxpPmYoa2l0KSA9IDQzODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWIyZThcdWM1YjQgXHVjOTExXHVjNWQwXHVjMTFjIEhhc2hcdWFjMTJcdWM3NzQgS1x1Yzc3OCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzU0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgSywgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLCAwICZsZTsgSyAmbHQ7IDI8c3VwPk08XC9zdXA+LCA2ICZsZTsgTSAmbGU7IDI1KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc0XHViYTc0XHVjMTFjIEhhc2hcdWFjMTJcdWM3NzQgS1x1Yzc3OCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YjJlOFx1YzViNFx1Yjg1Y1x1YjI5NCAmbGRxdW87ZHhsJnJkcXVvOywgJmxkcXVvO2hwaCZyZHF1bzssICZsZHF1bztseGQmcmRxdW87LCAmbGRxdW87eHB4JnJkcXVvOyBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwMDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIQVNIIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgTWlya28gaXMgc3R1ZHlpbmcgdGhlIGhhc2ggZnVuY3Rpb24gd2hpY2ggYXNzb2NpYXRlcyBudW1lcmljYWwgdmFsdWVzIHRvIHdvcmRzLiBUaGUgZnVuY3Rpb24gaXMgZGVmaW5lZCByZWN1cnNpdmVseSBpbiB0aGUgZm9sbG93aW5nIHdheTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mKCBlbXB0eSB3b3JkICkgPSAwJm5ic3A7PFwvbGk+XHJcblx0PGxpPmYoIHdvcmQgKyBsZXR0ZXIgKSA9ICggKCBmKCB3b3JkICkgKiAzMyApIFhPUiBvcmQoIGxldHRlciApICkgJSBNT0QmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgZnVuY3Rpb24gaXMgZGVmaW5lZCBmb3Igd29yZHMgdGhhdCBjb25zaXN0IG9mIG9ubHkgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFhPUiBzdGFuZHMgZm9yIHRoZSBiaXR3aXNlIFhPUiBvcGVyYXRvciAoaS5lLiAwMTEwIFhPUiAxMDEwID0gMTEwMCksIG9yZChsZXR0ZXIpIHN0YW5kcyBmb3IgdGhlIG9yZGluYWwgbnVtYmVyIG9mIHRoZSBsZXR0ZXIgaW4gdGhlIGFscGhhYmV0IChvcmQoYSkgPSAxLCBvcmQoeikgPSAyNikgYW5kIEEgJSBCIHN0YW5kcyBmb3IgdGhlIHJlbWFpbmRlciBvZiB0aGUgbnVtYmVyIEEgd2hlbiBwZXJmb3JtaW5nIGludGVnZXIgZGl2aXNpb24gd2l0aCB0aGUgbnVtYmVyIEIuIE1PRCB3aWxsIGJlIGFuIGludGVnZXIgb2YgdGhlIGZvcm0gMjxzdXA+TTxcL3N1cD4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvbWUgdmFsdWVzIG9mIHRoZSBoYXNoIGZ1bmN0aW9uIHdoZW4gTSA9IDEwOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmYoIGEgKSA9IDEmbmJzcDs8XC9saT5cclxuXHQ8bGk+ZiAoIGFhICkgPSAzMiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5mICgga2l0ICkgPSA0MzgmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5NaXJrbyB3YW50cyB0byBmaW5kIG91dCBob3cgbWFueSB3b3JkcyBvZiB0aGUgbGVuZ3RoIE4gdGhlcmUgYXJlIHdpdGggdGhlIGhhc2ggdmFsdWUgSy4gV3JpdGUgYSBwcm9ncmFtbWUgdG8gaGVscCBoaW0gY2FsY3VsYXRlIHRoaXMgbnVtYmVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgTiwgSyBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxMCwgMCAmbGU7IEsgJmx0OyAyPHN1cD5NPFwvc3VwPiwgNiAmbGU7IE0gJmxlOyAyNSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29uc2lzdCBvZiB0aGUgcmVxdWlyZWQgbnVtYmVyIGZyb20gdGhlIHRhc2suJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaG9zZSBhcmUgdGhlIHdvcmRzICZsZHF1bztkeGwmcmRxdW87LCAmbGRxdW87aHBoJnJkcXVvOywgJmxkcXVvO2x4ZCZyZHF1bzsgYW5kICZsZHF1bzt4cHgmcmRxdW87LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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