TopCoder problem "TheLongPalindrome" used in SRM 428 (Division I Level Two)



Problem Statement

    

John and Brus are studying string theory at the university. Their task is to create a list of all the palindromes that contain between 1 and n lowercase letters ('a'-'z'), inclusive. A palindrome is a string that reads the same forward and backward. Additionally, each palindrome in their list must contain no more than k distinct letters. Return the number of palindromes in the list modulo 1234567891.

 

Definition

    
Class:TheLongPalindrome
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int n, int k)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1,000,000,000, inclusive.
-k will be between 1 and 26, inclusive.
 

Examples

0)
    
1
1
Returns: 26
All palindromes in the list are single character strings.
1)
    
2
10
Returns: 52
Now we have single and double character palindromes.
2)
    
3
2
Returns: 728
A slightly longer list.
3)
    
44
7
Returns: 240249781

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10184

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13519&pm=10184

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Recursion