PalindromicSubseq2 | Topcoder Archive

Problem Statement

A palindrome is a string that reads the same forwards and backwards. For example, "abba" and "racecar" are palindromes.

An odd palindrome is a palindrome with an odd length. For example, "racecar" is an odd palindrome but "abba" is not. The middle letter of an odd palindrome is called its center.

Limak has a String s consisting of N lowercase English letters.

For each valid i, let X[i] be the number of palidromic subsequences of s such that their center is s[i].

In other words: For a fixed i, there are exactly 2^(N-1) ways to erase some characters of s other than the character s[i]. X[i] is the number of ways of erasing for which the string that remains to the left of s[i] is the reverse of the string that remains to the right of s[i].

For each i, compute the value Y[i] = ((i+1) * X[i]) modulo 1,000,000,007. Then, compute and return the bitwise XOR of all the values Y[i].

Definition

Class:: PalindromicSubseq2
Method:: solve
Parameters:: String
Returns:: int
Method signature:: int solve(String s)
(be sure your method is public)

Constraints

s will contain exactly N characters.
N will be between 1 and 3000, inclusive.
Each character in s will be a lowercase English letter 'a' - 'z'.

Examples

```
"axbcba"
```
```
Returns: 31
```
For this string we have X = {1, 2, 2, 4, 2, 1}. Thus, you should return the value (1*1) XOR (2*2) XOR (3*2) XOR (4*4) XOR (5*2) XOR (6*1) = 31. Here is an explanation why X[3] = 4: Given that we want to keep the character s[3], there are 32 possible subsequences of s. Among these there are 4 palindromes centered at s[3]: ...c.. a..c.a ..bcb. a.bcba
```
"eeeee"
```
```
Returns: 14
```
Here we have X[2] = 6. The six ways of erasing that produce a palindrome centered at s[2] are the following ones: ..e.. .ee.e .eee. e.e.e e.ee. eeeee Note that we count each way of erasing characters separately, even if different ways of erasing produce the same palindromic string. So, not all X[i] are equal to 6 here.
```
"tcoct"
```
```
Returns: 4
```
X[] = {1, 2, 4, 2, 1}
```
"zyzyzzzzxzyz"
```
```
Returns: 221
```
```
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
```
```
Returns: 1044407608
```
Note that in this case the answer exceeds the modulo value, because we return the XOR of modulo-ed values, without computing the modulo of that XOR.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.