시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 957 685 578 74.103%

문제

0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.

s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn

위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.

수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.

예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.

11100, 01110, 00111, 10111, 11101, 11011

입력

첫째 줄에 테스트 케이스의 수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 숫자 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 숫자는 n이고, 두 번째 숫자는 k이다. n은 100을 넘지 않는다.

출력

각 테스트 케이스에 대해 인접한 비트의 개수가 k인 수열 S의 개수를 한 줄에 하나씩 출력한다. 이 값은 2147483647보다 작거나 같다.

예제 입력 1

10
5 2
20 8
30 17
40 24
50 37
60 52
70 59
80 73
90 84
100 90

예제 출력 1

6
63426
1861225
168212501
44874764
160916
22937308
99167
15476
23076518
W3sicHJvYmxlbV9pZCI6IjI2OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzhcdWM4MTFcdWQ1NWMgXHViZTQ0XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+MFx1YWNmYyAxXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjQgU1x1YWMwMCBcdWM3ODhcdWIyZTQuIFNcdWM3NTggXHVjY2FiIFx1YzIxOFx1YjI5NCBzMVx1Yzc3NFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIxOFx1YjI5NCBzblx1Yzc3NFx1YjJlNC4gU1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViZTQ0XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5zPHN1Yj4xPFwvc3ViPipzPHN1Yj4yPFwvc3ViPiArIHM8c3ViPjI8XC9zdWI+KnM8c3ViPjM8XC9zdWI+ICsgczxzdWI+MzxcL3N1Yj4qczxzdWI+NDxcL3N1Yj4gKyAuLi4gKyBzPHN1Yj5uLTE8XC9zdWI+ICogczxzdWI+bjxcL3N1Yj48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzJkZFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjMjE4XHVjNWY0IFNcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2NcdWI0ZTRcdWM1YjQsIDAxMTEwMTEwMVx1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViZTQ0XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAzXHVjNzc0IFx1YjQxOFx1YWNlMCwgMTExMTAxMTAxXHVjNzQwIDQsIDAxMDEwMTAxMFx1Yzc0MCAwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IFNcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWFjZmMga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViZTQ0XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBrXHVjNzc4IFx1YzIxOFx1YzVmNCBTXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgblx1Yzc3NCA1XHVjNzc0XHVhY2UwLCBrXHVhYzAwIDJcdWM3NzRcdWJhNzQsIFx1YzIxOFx1YzVmNCBTXHVhYzAwIFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IDZcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4xMTEwMCwgMDExMTAsIDAwMTExLCAxMDExMSwgMTExMDEsIDExMDExPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQoMSZsdDs9VCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWMyMmJcdWM3OTAgMlx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IG5cdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IGtcdWM3NzRcdWIyZTQuIG5cdWM3NDAgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJlNDRcdWQyYjhcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIGtcdWM3NzggXHVjMjE4XHVjNWY0IFNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAyMTQ3NDgzNjQ3XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFkamFjZW50IEJpdCBDb3VudHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBhIHN0cmluZyBvZiBuIGJpdHMgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCB4PHN1Yj4zPFwvc3ViPiwgJmhlbGxpcDssIHg8c3ViPm48XC9zdWI+LCB0aGUgYWRqYWNlbnQgYml0IGNvdW50IG9mIHRoZSBzdHJpbmcgKEFkakJDKHgpKSBpcyBnaXZlbiBieSZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG54PHN1Yj4xPFwvc3ViPip4PHN1Yj4yPFwvc3ViPiArIHg8c3ViPjI8XC9zdWI+Kng8c3ViPjM8XC9zdWI+ICsgeDxzdWI+MzxcL3N1Yj4qeDxzdWI+NDxcL3N1Yj4gKyAmaGVsbGlwOyArIHg8c3ViPm4tMTxcL3N1Yj4qeDxzdWI+bjxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD53aGljaCBjb3VudHMgdGhlIG51bWJlciBvZiB0aW1lcyBhIDEgYml0IGlzIGFkamFjZW50IHRvIGFub3RoZXIgMSBiaXQuIEZvciBleGFtcGxlOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5BZGpCQygwMTExMDExMDEpID0gM1xyXG5BZGpCQygxMTExMDExMDEpID0gNFxyXG5BZGpCQygwMTAxMDEwMTApID0gMDxcL3ByZT5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB0YWtlcyBhcyBpbnB1dCBpbnRlZ2VycyBuIGFuZCBrIGFuZCByZXR1cm5zIHRoZSBudW1iZXIgb2YgYml0IHN0cmluZ3MgeCBvZiBuIGJpdHMgKG91dCBvZiAyXHUyMDdmKSB0aGF0IHNhdGlzZnkgQWRqQkMoeCkgPSBrLiBGb3IgZXhhbXBsZSwgZm9yIDUgYml0IHN0cmluZ3MsIHRoZXJlIGFyZSA2IHdheXMgb2YgZ2V0dGluZyBBZGpCQyh4KSA9IDI6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbjExMTAwLCAwMTExMCwgMDAxMTEsIDEwMTExLCAxMTEwMSwgMTEwMTE8XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgaXMgYSBzaW5nbGUgbGluZSB0aGF0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZGVjaW1hbCBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIChuKSBvZiBiaXRzIGluIHRoZSBiaXQgc3RyaW5ncywgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZGVjaW1hbCBpbnRlZ2VyIChrKSBnaXZpbmcgdGhlIGRlc2lyZWQgYWRqYWNlbnQgYml0IGNvdW50LiBUaGUgbnVtYmVyIG9mIGJpdHMgKG4pIHdpbGwgbm90IGJlIGdyZWF0ZXIgdGhhbiAxMDAgYW5kIHRoZSBwYXJhbWV0ZXJzIG4gYW5kIGsgd2lsbCBiZSBjaG9zZW4gc28gdGhhdCB0aGUgcmVzdWx0IHdpbGwgZml0IGluIGEgc2lnbmVkMzItYml0IGludGVnZXIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIG4tYml0IHN0cmluZ3Mgd2l0aCBhZGphY2VudCBiaXQgY291bnQgZXF1YWwgdG8gay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest F번

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