Palindrome Word Sequences
Time limit2sMemory limit128 MB
Count ordered sequences of given words, reused any number of times, whose concatenation has exact length L and forms a palindrome.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String matching, String, Combinatorics
- Solved
- No attempts yet
Problem
A palindrome is a string that reads the same forward and backward.
You are given N distinct uppercase English words. Count how many ways there are to concatenate the given words, in any order, so that the resulting string has length L and is a palindrome.
Each word may be used more than once. If two sequences of chosen words are different, they are counted as different ways even when their concatenated string is identical.
Input
The first line contains N, the number of words. The second line contains L, the required length of the final string. Each of the next N lines contains one distinct uppercase English word.
- 1 <= N <= 50
- 1 <= L <= 30
- Each word has length between 1 and 15, inclusive.
- Every word consists only of uppercase English letters.
Output
Print the number of ways to concatenate the given words into a palindrome of length L. The answer does not exceed 2,100,000,000.