시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB25581857154276.946%

문제

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과 k는 100을 넘지 않는 자연수이다.

출력

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

예제 입력 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+XHJcblxyXG48cD4xMTEwMCwgMDExMTAsIDAwMTExLCAxMDExMSwgMTExMDEsIDExMDExPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzIxOCAyXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgblx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQga1x1Yzc3NFx1YjJlNC4gblx1YWNmYyBrXHViMjk0IDEwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNzc4XHVjODExXHVkNTVjIFx1YmU0NFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAga1x1Yzc3OCBcdWMyMThcdWM1ZjQgU1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDIsMTQ3LDQ4Myw2NDdcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNjk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWRqYWNlbnQgQml0IENvdW50cyIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIGEgc3RyaW5nIG9mIG4gYml0cyB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHg8c3ViPjM8XC9zdWI+LCAmaGVsbGlwOywgeDxzdWI+bjxcL3N1Yj4sIHRoZSBhZGphY2VudCBiaXQgY291bnQgb2YgdGhlIHN0cmluZyAoQWRqQkMoeCkpIGlzIGdpdmVuIGJ5Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbng8c3ViPjE8XC9zdWI+Kng8c3ViPjI8XC9zdWI+ICsgeDxzdWI+MjxcL3N1Yj4qeDxzdWI+MzxcL3N1Yj4gKyB4PHN1Yj4zPFwvc3ViPip4PHN1Yj40PFwvc3ViPiArICZoZWxsaXA7ICsgeDxzdWI+bi0xPFwvc3ViPip4PHN1Yj5uPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPndoaWNoIGNvdW50cyB0aGUgbnVtYmVyIG9mIHRpbWVzIGEgMSBiaXQgaXMgYWRqYWNlbnQgdG8gYW5vdGhlciAxIGJpdC4gRm9yIGV4YW1wbGU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbkFkakJDKDAxMTEwMTEwMSkgPSAzXHJcbkFkakJDKDExMTEwMTEwMSkgPSA0XHJcbkFkakJDKDAxMDEwMTAxMCkgPSAwPFwvcHJlPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIHRha2VzIGFzIGlucHV0IGludGVnZXJzIG4gYW5kIGsgYW5kIHJldHVybnMgdGhlIG51bWJlciBvZiBiaXQgc3RyaW5ncyB4IG9mIG4gYml0cyAob3V0IG9mIDJcdTIwN2YpIHRoYXQgc2F0aXNmeSBBZGpCQyh4KSA9IGsuIEZvciBleGFtcGxlLCBmb3IgNSBiaXQgc3RyaW5ncywgdGhlcmUgYXJlIDYgd2F5cyBvZiBnZXR0aW5nIEFkakJDKHgpID0gMjombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuMTExMDAsIDAxMTEwLCAwMDExMSwgMTAxMTEsIDExMTAxLCAxMTAxMTxcL3ByZT5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBpcyBhIHNpbmdsZSBsaW5lIHRoYXQgY29udGFpbnMgYSBkZWNpbWFsIGludGVnZXIgZ2l2aW5nIHRoZSBudW1iZXIgKG4pIG9mIGJpdHMgaW4gdGhlIGJpdCBzdHJpbmdzLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSwgZm9sbG93ZWQgYnkgYSBkZWNpbWFsIGludGVnZXIgKGspIGdpdmluZyB0aGUgZGVzaXJlZCBhZGphY2VudCBiaXQgY291bnQuIFRoZSBudW1iZXIgb2YgYml0cyAobikgd2lsbCBub3QgYmUgZ3JlYXRlciB0aGFuIDEwMCBhbmQgdGhlIHBhcmFtZXRlcnMgbiBhbmQgayB3aWxsIGJlIGNob3NlbiBzbyB0aGF0IHRoZSByZXN1bHQgd2lsbCBmaXQgaW4gYSBzaWduZWQzMi1iaXQgaW50ZWdlci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zJm5ic3A7dGhlIG51bWJlciBvZiBuLWJpdCBzdHJpbmdzIHdpdGggYWRqYWNlbnQgYml0IGNvdW50IGVxdWFsIHRvIGsuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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