TopCoder srm 708c PalindromicSubseq2

problem

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 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].

how to solve

To solve this problem using two hash-table. I can solve this problem in O(n)

code