PalindromicSubseq
SRM 708 · 2016-12-07 · by Errichto
Problem Statement
A palindrome is a string that reads the same forwards and backwards. For example, "abba" and "racecar" are palindromes.
Limak has a
For each valid i, let X[i] be the number of palidromic subsequences of s that contain the i-th character of s.
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 is a palindrome.
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].
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'.
"aaba" Returns: 30
For this string we have X = {5, 5, 3, 6}. Thus, you should return the value (1*5) XOR (2*5) XOR (3*3) XOR (4*6) = 5 XOR 10 XOR 9 XOR 24 = 30. Here is an explanation why X[0] = 5: Given that we want to keep the character s[0], there are 8 possible subsequences of s: a... * a..a * a.b. a.ba * aa.. * aa.a * aab. aaba Five of these subsequences (marked by stars) are palindromes. Note that there are two different ways to produce the palindrome "aa".
"abcd" Returns: 4
X[i] = 1 for all i. You should return (1*1) XOR (2*1) XOR (3*1) XOR (4*1) = 1 XOR 2 XOR 3 XOR 4 = 4.
"tcoct" Returns: 60
X[] = {7, 6, 4, 6, 7}
"zyzyzzzzxzyz" Returns: 717
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" Returns: 1025495382
If all characters are the same, all 2^N subsequences are palindromes. For every index i all 2^(N-1) subseqeunces that contain it are palindromes. It means that X[i] = 2^(N-1) for all i. 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.
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PalindromicSubseq with a public method int solve(string s) · 45 test cases · 2 s / 256 MB per case