Links:
CUPACO - Cumulative Palindrome Count
Author / Editorialist - McDic
Difficulty:
Medium-Hard
Pre-requisites:
Combinatorics and some maths
Statement Abstraction
Let s to be “abaabbaaaabbbb…” and f(x) to be number of possible palindrome substring segments in s[1 \ldots x]. Calculate \sum_{i=1}^{n} f(i) \bmod{10^9 + 7}.
Explanation
Let f(x) = o(x) + t(x), where o(x) is the number of single-charactered palindromes(“aaaa”, “bb”, etc) and t(x) is the number of three-charactered palindromes(“aaabbbbaaa”, etc).
The first key point is, there is no other kind(except for two types described above) of palindrome substrings possible, because there is no two same segments in whole s. The second key point is, we can separate o(x) and t(x) in terms of calculation because they are independent.
Let’s assume following situation: s = “…aa b…b aa…aa bb…bb”, where each segment’s end index are ppp, pp, p, and x. (s[\ldots ppp] is “…aa”, s[ppp+1 \ldots pp] is “b…b”, s[pp+1 \ldots p] is “aa…aa”, and s[p+1 \ldots x] is “bb…bb”) Then we can construct following formula:
- o(i) = o(p) + \binom{i-p+1}{2}, because new cases on last segment selection is added.
- t(i) = t(p) + \text{min}(pp-ppp, i-p), because new cases on “bb…aa…bb” is added.
But our goal is to calculate sum of f(x). So let’s make following formula:
- \sum_{i=p+1}^{x} o(i) = o(p) \cdot (x-p) + \sum_{i=1}^{x-p} \binom{i+1}{2} = o(p) \cdot (x-p) + \frac{1}{6} \cdot (x-p) \cdot (x-p+1) \cdot (x-p+2).
- \sum_{i=p+1}^{x} t(i) = t(p) \cdot (x-p) + (1 + 2 + \ldots + R_{1}) + R_{2} = t(p) \cdot (x-p) + \frac{1}{2} \cdot R_{1} \cdot (R_{1} + 1) + R_{2}. Value of R_{1} and R_{2} depends on which (pp-ppp and x-p) is bigger.
So in each segment, you calculate following formulas to get sum of f value in segments and last f value of segment, then recursively pass to next segment until you reach index n. You have maximum \log n segments, so time complexity is O(\log n) per test case.
Author’s Source Code
https://www.codechef.com/viewsolution/28914218