시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 189 150 133 82.099%

문제

양의 정수 N의 파티션은 합이 N이 되는 수열을 말한다. 보통 숫자 사이에 +를 넣어서 나타낸다. 예를 들면

15 = 1+2+3+4+5 = 1+2+1+7+1+2+1 이다.

어떤 파티션을 앞에서 읽을 때와 뒤에서 읽을 때가 같으면 이 파티션을 팰린드롬 파티션이라고 한다. 위의 예에서 첫 번째 파티션은 팰린드롬 파티션이 아니지만, 두 번째 파티션은 팰린드롬 파티션이다.

어떤 파티션이 m개의 정수로 이루어져 있다면, 왼쪽 절반은 처음 floor(m/2)개의 원소, 오른쪽 절반은 마지막 floor(m/2)개의 원소이다. 

재귀적인 팰린드롬 파티션은 어떤 파티션이 팰린드롬이면서, 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나, 비어있을 때 이다. 모든 정수는 적어도 2개의 재귀적인 팰린드롬 파티션을 항상 갖는다. (n과, 1 n개) 

7의 재귀적인 팰린드롬 파티션은 다음과 같이 6가지가 있다.

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

어떤 수 N을 입력받은 다음에, 재귀적인 팰린드롬 파티션의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 양의 정수 1개로 이루어져있고, 이 수가 문제에서 설명한 N이고, 1,000보다 작거나 같다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 N의 재귀적인 팰린드롬 파티션의 개수를 출력한다.

예제 입력 1

3
4
7
20

예제 출력 1

4
6
60
W3sicHJvYmxlbV9pZCI6IjI3MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVkMzBjXHVkMmYwXHVjMTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWM3NTggXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQwIFx1ZDU2OVx1Yzc3NCBOXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWJjZjRcdWQxYjUgXHVjMjJiXHVjNzkwIFx1YzBhY1x1Yzc3NFx1YzVkMCArXHViOTdjIFx1YjEyM1x1YzViNFx1YzExYyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQ8XC9wPlxyXG5cclxuPHA+MTUgPSAxKzIrMys0KzUgPSAxKzIrMSs3KzErMisxIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHVjNzdkXHVjNzQ0IFx1YjU0Y1x1YzY0MCBcdWI0YTRcdWM1ZDBcdWMxMWMgXHVjNzdkXHVjNzQ0IFx1YjU0Y1x1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzQgXHVjNzc0IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0MCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzc0IFx1YzU0NFx1YjJjOFx1YzljMFx1YjljYywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWQzMGNcdWQyZjBcdWMxNThcdWM3NDAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NCBtXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0XHViYTc0LCBcdWM2N2NcdWNhYmQgXHVjODA4XHViYzE4XHVjNzQwIFx1Y2M5OFx1Yzc0YyBmbG9vcihtXC8yKVx1YWMxY1x1Yzc1OCBcdWM2ZDBcdWMxOGMsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM4MDhcdWJjMThcdWM3NDAgXHViOWM4XHVjOWMwXHViOWM5IGZsb29yKG1cLzIpXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVhZGMwXHVjODAxXHVjNzc4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyBcdWQzMGNcdWQyZjBcdWMxNThcdWM3NDAgXHVjNWI0XHViNWE0IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWJhNzRcdWMxMWMsIFx1YzY3Y1x1Y2FiZCBcdWM4MDhcdWJjMThcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzgwOFx1YmMxOFx1Yzc3NCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3NzggXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHVhYzcwXHViMDk4LCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM3NDQgXHViNTRjIFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YWMxY1x1Yzc1OCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3NzggXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWQ1NmRcdWMwYzEgXHVhYzE2XHViMjk0XHViMmU0LiAoblx1YWNmYywgMSBuXHVhYzFjKSZuYnNwOzxcL3A+XHJcblxyXG48cD43XHVjNzU4IFx1YzdhY1x1YWRjMFx1YzgwMVx1Yzc3OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgNlx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjcsIDErNSsxLCAyKzMrMiwgMSsxKzMrMSsxLCAzKzErMywgMSsxKzErMSsxKzErMTxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjMjE4IE5cdWM3NDQgXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YzVkMCwgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzc4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyBcdWQzMGNcdWQyZjBcdWMxNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmx0Oz0gVCAmbHQ7PSAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IDFcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHVhYzAwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgTlx1Yzc3NFx1YWNlMCwgMSwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgTlx1Yzc1OCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3NzggXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWN1cnNpdmVseSBQYWxpbmRyb21pYyBQYXJ0aXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHBhcnRpdGlvbiBvZiBhIHBvc2l0aXZlIGludGVnZXIgTiBpcyBhIHNlcXVlbmNlIG9mIGludGVnZXJzIHdoaWNoIHN1bSB0byBOLCB1c3VhbGx5IHdyaXR0ZW4gd2l0aCBwbHVzIHNpZ25zIGJldHdlZW4gdGhlIG51bWJlcnMgb2YgdGhlIHBhcnRpdGlvbi4gRm9yIGV4YW1wbGU8XC9wPlxyXG5cclxuPHA+MTUgPSAxKzIrMys0KzUgPSAxKzIrMSs3KzErMisxPFwvcD5cclxuXHJcbjxwPkEgcGFydGl0aW9uIGlzIHBhbGluZHJvbWljIGlmIGl0IHJlYWRzIHRoZSBzYW1lIGZvcndhcmQgYW5kIGJhY2t3YXJkLiBUaGUgZmlyc3QgcGFydGl0aW9uIGluIHRoZSBleGFtcGxlIGlzIG5vdCBwYWxpbmRyb21pYyB3aGlsZSB0aGUgc2Vjb25kIGlzLiBJZiBhIHBhcnRpdGlvbiBjb250YWluaW5nIG0gaW50ZWdlcnMgaXMgcGFsaW5kcm9taWMsIGl0cyBsZWZ0IGhhbGYgaXMgdGhlIGZpcnN0IGZsb29yKG1cLzIpIGludGVnZXJzIGFuZCBpdHMgcmlnaHQgaGFsZiBpcyB0aGUgbGFzdCBmbG9vcihtXC8yKSBpbnRlZ2VycyAod2hpY2ggbXVzdCBiZSB0aGUgcmV2ZXJzZSBvZiB0aGUgbGVmdCBoYWxmLiAoZmxvb3IoeCkgaXMgdGhlIGdyZWF0ZXN0IGludGVnZXIgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIHguKTxcL3A+XHJcblxyXG48cD5BIHBhcnRpdGlvbiBpcyByZWN1cnNpdmVseSBwYWxpbmRyb21pYyBpZiBpdCBpcyBwYWxpbmRyb21pYyBhbmQgaXRzIGxlZnQgaGFsZiBpcyByZWN1cnNpdmVseSBwYWxpbmRyb21pYyBvciBlbXB0eS4gTm90ZSB0aGF0IGV2ZXJ5IGludGVnZXIgaGFzIGF0IGxlYXN0IHR3byByZWN1cnNpdmVseSBwYWxpbmRyb21pYyBwYXJ0aXRpb25zIG9uZSBjb25zaXN0aW5nIG9mIGFsbCBvbmVzIGFuZCBhIHNlY29uZCBjb25zaXN0aW5nIG9mIHRoZSBpbnRlZ2VyIGl0c2VsZi4gVGhlIHNlY29uZCBleGFtcGxlIGFib3ZlIGlzIGFsc28gcmVjdXJzaXZlbHkgcGFsaW5kcm9taWMuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgcmVjdXJzaXZlbHkgcGFsaW5kcm9taWMgcGFydGl0aW9ucyBvZiA3IGFyZTo8XC9wPlxyXG5cclxuPHA+NywgMSs1KzEsIDIrMysyLCAxKzErMysxKzEsIDMrMSszLCAxKzErMSsxKzErMSsxPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB0YWtlcyBhcyBpbnB1dCBhbiBpbnRlZ2VyIE4gYW5kIG91dHB1dHMgdGhlIG51bWJlciBvZiByZWN1cnNpdmVseSBwYWxpbmRyb21pYyBwYXJ0aXRpb25zIG9mIE4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4sICgxICZwb3VuZDsgTiAmcG91bmQ7IDEwMDApIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQgY29udGFpbmluZyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIGZvciB3aGljaCB0aGUgbnVtYmVyIG9mIHJlY3Vyc2l2ZWx5IHBhbGluZHJvbWljIHBhcnRpdGlvbnMgaXMgdG8gYmUgZm91bmQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHlvdSBzaG91bGQgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBkYXRhIHNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc3BhY2UgYW5kIHRoZSBudW1iZXIgb2YgcmVjdXJzaXZlbHkgcGFsaW5kcm9taWMgcGFydGl0aW9ucyBvZiB0aGUgaW5wdXQgdmFsdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2008 Greater New York Programming Contest D번