Beautiful Patterns (Hard Version)

Let

$q=m^{-1} \pmod p.$

For a substring of length $L$, being a palindrome forces exactly $\lfloor L/2\rfloor$ pairs of characters to be equal. So

$\Pr(\text{length }L\text{ substring is palindrome})=q^{\lfloor L/2\rfloor}.$

Define

$C=\sum_I X_I,$

where $X_I$ is the indicator that interval $I$ is palindromic. We need

$\mathbb E[C^2]=\sum_{I,J}\mathbb E[X_I X_J]=\sum_{I,J}\Pr(I,J\text{ are both palindromes}).$

The whole problem is figuring out when two palindrome events are independent.

The Big Trick: Almost Everything Is Independent

For one interval, group positions that must be equal in a palindrome. For example, a length $7$ interval has $4$ groups: three symmetric pairs and the middle singleton. In general, a length $L$ palindrome has

$\lceil L/2\rceil$

free groups.

Now take two substrings $S_1$ and $S_2$.

Make a bipartite graph:

• left vertices are the equality-groups of $S_1$,
• right vertices are the equality-groups of $S_2$,
• every shared character position creates an edge between its group in $S_1$ and its group in $S_2$.

If the two substrings have different centers, this graph is a forest. Why? Walking two steps in this graph corresponds to reflecting around one center, then reflecting around the other center. The composition of two different reflections is a nonzero translation. A nonzero translation cannot bring you back to the same position, so cycles are impossible. That is the clean version; the messy version is just the same fact wearing a fake mustache.

Let the lengths be $a$ and $b$, and let their overlap length be $t$.

For non-concentric substrings, the graph has

$\lceil a/2\rceil+\lceil b/2\rceil$

vertices and $t$ edges, so because it is a forest, it has

$\lceil a/2\rceil+\lceil b/2\rceil-t$

connected components. These components are exactly the final free color choices.

The union has $a+b-t$ positions, so the probability exponent is

$$(a+b-t)-\left(\lceil a/2\rceil+\lceil b/2\rceil-t\right) =\lfloor a/2\rfloor+\lfloor b/2\rfloor.$$

That is exactly the product of the two individual probabilities.

So every non-concentric pair behaves independently. Even overlapping ones. That is the part that feels illegal, but it is true.

Only Same-Center Pairs Need Fixing

If two substrings have the same center, one is nested inside the other.

Represent a centered substring by its radius

$r=\left\lfloor \frac{L}{2}\right\rfloor.$

A palindrome of larger radius automatically implies every smaller palindrome with the same center. Therefore, for two radii $a,b$ at the same center,

$\Pr(\text{both})=q^{\max(a,b)}.$

But if we first pretend everything is independent, that pair was counted as

$q^{a+b}.$

So the correction for this ordered radius pair is

$q^{\max(a,b)}-q^{a+b}.$

Base Independent Sum

Let

$A=\sum_{L=1}^{n}(n-L+1)q^{\lfloor L/2\rfloor}.$

This is $\mathbb E[C]$.

If all pairs were independent, the answer would be

$A^2.$

Now add corrections for same-center pairs only.

Odd Centers

For a character center, allowed radii are

$0,1,2,\dots,R.$

Here radius $0$ is the one-character substring, which is always a palindrome.

For all ordered pairs of radii in $[0,R]$:

$$\sum_{a=0}^{R}\sum_{b=0}^{R} q^{\max(a,b)} =\sum_{k=0}^{R}(2k+1)q^k,$$

because the number of ordered pairs with $\max(a,b)=k$ is

$(k+1)^2-k^2=2k+1.$

Also,

$$\sum_{a=0}^{R}\sum_{b=0}^{R} q^{a+b} =\left(\sum_{k=0}^{R}q^k\right)^2.$$

So the odd-center correction is

$$F_0(R)=\sum_{k=0}^{R}(2k+1)q^k-\left(\sum_{k=0}^{R}q^k\right)^2.$$

Even Centers

For a gap center, allowed radii are

$1,2,\dots,R.$

There is no radius $0$ substring because empty substrings do not count.

Similarly,

$$F_1(R)=\sum_{k=1}^{R}(2k-1)q^k-\left(\sum_{k=1}^{R}q^k\right)^2.$$

The count $2k-1$ comes from

$k^2-(k-1)^2=2k-1.$

Putting It Together

For every character position $i$, the maximum odd radius is

$R=\min(i,n-1-i)$

using zero-indexed positions.

For every gap after position $i-1$ and before position $i$, the maximum even radius is

$R=\min(i,n-i).$

The answer is

$$A^2+ \sum_{\text{odd centers}}F_0(R)+ \sum_{\text{even centers}}F_1(R).$$

All powers and sums are computed modulo $p$. Since $p$ is prime and $m<p$, the inverse $m^{-1}\pmod p$ exists.

Complexity

Precompute powers of $q$, the two correction arrays, and then scan all centers.

Time:

$O(n)$

per test case.

Memory:

$O(n).$

Across all test cases, this is fine because the total $n$ is at most $10^6$. The hard version looks scary, but once non-concentric pairs stop pretending to be a problem, it folds pretty cleanly.