PalindromicSubseq2
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.
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
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].
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'.
"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.
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PalindromicSubseq2 with a public method int solve(string s) · 44 test cases · 2 s / 256 MB per case