LongPalindromes

TCO19 SRM 740 · 2018-10-19 · by misof

TCO19 SRM 740 · 2018-10-19 · by misof · Dynamic Programming, Math

Show categories

Class Name: LongPalindromes

Return Type: int

Method Name: count

Arg Types: (int, string)

Problem Statement

There is a string written on a sheet of paper. Katka has an eraser. She would like to erase some (possibly none or all) of the characters in such a way that the remaining letters will form a palindrome. Count the number of ways in which she can do it.

There is a catch: Katka's string is very long.

You are given the int repeats and the String pattern. Katka's string is obtained by concatenating repeats consecutive copies of the string pattern.

Compute and return the number of ways in which Katka can produce a palindrome, modulo 10^9 + 7.

Notes

A palindrome is a string that reads the same forwards and backwards. In particular, the empty string is also a palindrome.

Constraints

pattern will have between 1 and 50 characters, inclusive.
Each character in pattern will be a lowercase English letter ('a'-'z').
repeats will be between 1 and 10^9, inclusive.

Examples

1
"blob"
Returns: 8

The eight valid ways of erasing are the following ones (with periods representing erased letters): .... b... .l.. ..o. ...b b..b bl.b b.ob

1
"various"
Returns: 8

All the letters are distinct, so Katka must erase all except for at most one.

30
"aa"
Returns: 536396504

Katka's string consists of 60 occurrences of the letter 'a'. Each of the 2^60 possible ways of erasing some of them produces a palindrome.

3
"abac"
Returns: 343

987654321
"qwrtyuqertyuiqeqwertyuqwertzuiqrtyuiopopioqwertyui"
Returns: 14709905

Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LongPalindromes with a public method int count(int repeats, string pattern) · 82 test cases · 2 s / 256 MB per case