Beautiful Patterns (Easy Version)

Let

$X=\sum_I [I\text{ is palindrome}],$

where $I$ runs over all non-empty subsegments. The beauty is $X^2$, so

$E[X^2]=\sum_I\sum_J P(I\text{ and }J\text{ are both palindromes}).$

So yeah, $E[X]^2$ is bait. Overlapping palindromes are not independent. Math saw that shortcut and threw it in the trash.

One interval

A segment of length $L$ is a palindrome iff its mirrored positions match:

$s_l=s_r,\quad s_{l+1}=s_{r-1},\quad \ldots$

That gives exactly $\lfloor L/2\rfloor$ independent equality constraints, hence

$P(\text{length }L\text{ segment is palindrome})=m^{-\lfloor L/2\rfloor}.$

Let

$w(L)=m^{-\lfloor L/2\rfloor}.$

If all pairs of intervals behaved independently, the answer would be

$S^2,\qquad S=\sum_I w(|I|).$

This is almost right. The word almost is doing work.

When do two intervals actually depend?

Represent a palindrome condition as equality edges. For interval $[l,r]$, we add edges

$l+i \leftrightarrow r-i.$

All these edges have the same doubled center $l+r$.

Take two intervals. If their centers are different, their two reflection systems have no duplicate equality edges and no cycles. A quick way to see it: composing two different reflections gives a non-zero translation. Repeating a non-zero translation cannot bring a position back to itself, so no cycle means no redundant equality constraint.

Therefore, if two intervals have different centers, their probabilities multiply:

$P(I,J)=m^{-x-y},$

where

$x=\left\lfloor\frac{|I|}{2}\right\rfloor,\qquad y=\left\lfloor\frac{|J|}{2}\right\rfloor.$

Same center correction

If two intervals have the same center, they are nested. The smaller interval's mirror equalities are a subset of the larger interval's equalities. So both are palindromes iff the larger one is palindromic.

Thus

$P(I,J)=m^{-\max(x,y)}.$

But $S^2$ counted this pair as

$m^{-x-y}.$

So we can do:

$\text{answer}=S^2+\sum_{\text{centers}}\left(\sum_{I,J\text{ at this center}}m^{-\max(x_I,x_J)}-\left(\sum_{I\text{ at this center}}m^{-x_I}\right)^2\right).$

That fixes exactly the pairs that $S^2$ got wrong.

Counting intervals at one center

Use $0$-indexed positions. An interval $[l,r]$ has doubled center

$c=l+r,$

so $c$ ranges from $0$ to $2n-2$.

For a fixed center, each possible interval has a unique exponent

$x=\left\lfloor\frac{r-l+1}{2}\right\rfloor.$

If $c$ is even, the center is on a character, so the exponents are

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

If $c$ is odd, the center is between two characters, so the exponents are

$1,2,\ldots,R.$

Let

$lo=c\bmod 2,$

and

$R=\left\lfloor\frac{\min(c,2n-2-c)+lo}{2}\right\rfloor.$

Then the exponents for this center are exactly $lo,lo+1,\ldots,R$.

For this center, define $q=m^{-1}$. The independent same-center contribution already present in $S^2$ is

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

The correct same-center contribution is

$\sum_{x=lo}^{R}\sum_{y=lo}^{R}q^{\max(x,y)}.$

Group by $k=\max(x,y)$. The number of ordered pairs with maximum exactly $k$ is

$2(k-lo)+1.$

So the correct contribution is

$\sum_{k=lo}^{R}(2(k-lo)+1)q^k.$

Algorithm

1. Compute $q=m^{-1}\pmod p$ using Fermat's theorem.
2. Precompute $q^k$ for $0\le k\le n$.
3. Compute

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

4. Start with $ans=S^2$.
5. For every center $c$, add the correction:

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

Everything is modulo $p$. Complexity is $O(n)$ per test case after precomputing prefix sums. The easy version gives $n\le 2000$, so this is comfortably overkill in the best way.