No Do not solve me, I am hard!
All submissions for this problem are available.
Wade after being mutated by AJAX was in the search of AJAX (Francis Freeman) so he went up to different people to discover about him to have his disfigurement cured. He becomes a masked vigilante, takes the alias "Deadpool". Deadpool approaches the recruiter from a secret program that approached Wade aka Deadpool, offering an experimental cure for his cancer. He tells Dead pool about the roads that AJAX passes through frequently which are palindromes coincidentally.
Dead pool started to see carefully for all palindromes in the string that the agent gave him. For each occurrence of each palindrome in the string he wrote a pair --- the position of the start and the position of end of this occurrence in the string. Dead pool called each occurrence of each palindrome he found in the text sub palindrome. When he found all the sub palindromes, he started to find out how many different pairs among these sub palindromes cross. Two sub palindromes cross if they cover common positions in the text. No palindrome can cross itself.
Let's look at what actions are, performed by Dead pool, by the example of text babb. At first he wrote out all sub palindromes:
b — 1xx1 bab — 1xx3 a — 2xx2 b — 3xx3 bb — 3xx4 b — 4xx4
Then Dead Pool counted the amount of different pairs among these sub palindromes that cross for each pair. These pairs were six:
1. 1xx1 cross with 1xx3 2. 1xx3 cross with 2xx2 3. 1xx3 cross with 3xx3 4. 1xx3 cross with 3xx4 5. 3xx3 cross with 3xx4 6. 3xx4 cross with 4xx4
Since it is very frustrating to write all actions on paper, Dead pool wants you to help him write a program that can find out the count of different sub palindrome pairs that cross. Two sub palindrome pairs are considered different (distinct) if one of the pairs contains a sub palindrome that the other does not.
The first input line contains T the number of test cases. The second input line contains integer X (length of the text). The following line contains X lower-case Latin letters (from a to z).
In one line output the count of different pairs of two sub palindromes that cross each other. Output the answer % (modulo) 51123987.
- T ≤ 20
- 1 ≤ X ≤ 2*10^6
Input: 2 4 babb 2 aa Output: 6 2
Problem Setter : Sunny Karira
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.