# Enigma 2020 CUPACO editorial

CUPACO - Cumulative Palindrome Count
Author / Editorialist - McDic

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

2 Likes