Recursive Palindrome Partitions
Time limit1sMemory limit128 MB
Count recursive palindrome partitions of N, where a partition is valid if it is a palindrome and both halves are recursively valid.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Recursion, Combinatorics, Math
- Solved
- No attempts yet
Problem
A partition of a positive integer N is a sequence of positive integers whose sum is N. It is usually written by placing + between adjacent values.
A partition is a palindrome partition if reading its values from left to right gives the same sequence as reading them from right to left.
For a partition of length m, the left half consists of the first floor(m / 2) values, and the right half consists of the last floor(m / 2) values. If the length is odd, the middle value belongs to neither half.
A recursive palindrome partition is a partition that satisfies both conditions below.
- The whole partition is a palindrome.
- The left half and the right half are either empty or are themselves recursive palindrome partitions.
The partition consisting only of N and the partition consisting of N copies of 1 always satisfy the condition. Given a positive integer N, compute the number of recursive palindrome partitions of N.
Input
The first line contains the number of test cases T. (1 <= T <= 1,000)
Each of the next T lines contains one positive integer N. (1 <= N <= 1,000)
Output
For each test case, print the number of recursive palindrome partitions of N on its own line.