[Unofficial Editorial] PALIND from LoC April 2018

combinatorics
editorial
exponentiation
locapr18
modular
number
number-theory
probability

#1

Mathematical explanation


The points (or gain) for each win is X_l=1 where l is the length of the String. (Points for loss is 0).
Expectation is the weighted sum of the points, the weights being the probability of each event.
Precisely, the expected number of points for N-length palindrome is E_N=\sum_{i=1}^{N} P_iX_i=\sum_{i=1}^NP_i , where P_i is the probability to get the string with length=i as a palindrome. So we have to calculate P_l.

Consider a string of length l. The sample space is of size 26^l as we have 26 character choices for every position. If l is odd, then number of palindromes of length l is 26^{l+1\over 2} [Just decide the characters of the positions 1,2,\dots, {l+1\over 2} and the remainder spaces are filled symmetrically]. If l is even, then it is enought to fill the positions 1,2,\dots,l/2 and fill the remainder symmetrically to get palindrome. So we have

P_k= \left\{{26^{1-k\over 2}, 2 ot|k \\ 26^{-{k\over 2}},2|k} \right.

So, we observe that P_k=26^{-\left\lfloor {k\over 2} \right\rfloor }

\mathbb{1:}\\E_N=P_1+P_2+\dots +P_N=\left\{ {1+2\left(26^{-1}+26^{-2}+\dots+26^{-\left\lfloor {k\over 2} \right\rfloor }\right), extrm{ if }2 ot|N \\ 1+2\left(26^{-1}+26^{-2}+\dots+26^{-\left\lfloor {k\over 2} \right\rfloor+1}\right)+26^{-\left\lfloor {k\over 2} \right\rfloor }, extrm{ if } 2|N}\right.

Let x=\lfloor k/2 \rfloor. After simplyfying we will have,

\mathbb{2:}\\E_N=\left\{ {1+2\cdot\frac{26^x-1}{26^x\cdot 25}, extrm{ if }2 ot|N \\ 1+2\cdot\frac{26^x-1}{26^x\cdot 25}-\frac{1}{26^x}, extrm{ if }2|N} \right.

To compute the inverses, we have to use Fermat’s little theorem:
a^{p-1}\equiv 1\pmod p\forall a\in \mathbb{N}, (a,p)=1

So we will have the two parts of expression (2) as congruent to \left(1+2\cdot(26^x-1)\cdot25^{p-2}\cdot26^{p-1-x}\right)\pmod p and \left(1+2\cdot(26^x-1)\cdot25^{m-2}\cdot26^{m-1-x}-26^{p-1-x}\right)\pmod p


Coding


To use make the above computation faster, use the modular exponentiation. This is suitable as 10^9+7 is prime.

Here goes the code for 50 points wherein the computation has been done with the expression labelled as 1: Partial

Here goes the code for 100 points using simplified expression labelled as 2: Full