Simple Math, Matrix Exponentiation
Find the number of palindromic strings that can be made of length N, or less.
We can fix the first ciel(N/2) characters of the string as we want, and the rest of the string is simply forced.
Also, each string we get by fixing the first ciel(N/2) characters is a unique palindromic string.
Thus, we can find the number of palindromic strings of each length
F(n) = 26ceil(n/2)
Now, we need to find the summation of this result for all n from 1 to N to find all the palindromic strings of length N, or less.
SUMMA( F(n), 1 ≤ n ≤ N ) = 2*SUMMA( 26n, 1 ≤ n ≤ ceil(N/2) ), for even N 2*SUMMA( 26n, 1 ≤ n ≤ floor(N/2) ) + 26ceil(N/2) for odd N
We know that we can find ab for a large b by repeated squaring. The problem now reduces to calculating the following
S(n) = SUMMA( 26n, 1 ≤ n ≤ T )
There are two ways to find the result.
METHOD 1: Matrix Exponentiation
S(n) = 26, for n = 1 = 26*S(n-1) + 26
We can build the matrix equation as below
| S(n+1) | = | 26 26 | * | S(n) | | 1 | | 0 1 | | 1 |
Thus, to find the result, we can calculate
| 26 26 |T | 0 1 |
By repeated squaring of matrices. The results need to be found modulo 1000000007. Since all calculations are sum or product only, the drill should be straightforward.
METHOD 2: Sum of Geometric Progression
S(T) = 26*(26T - 1) / 25
Calculating the numerator modulo 1000000007 is pretty straight forward. We use repeated squaring for the exponent part.
But, to the uninitiated it might be confusing as to why can we get away with calculating the residue of the numerator considering we are yet to divide it by 25.
Here, we apply the concept of modular arithmetic inverses. These are well defined for residues modulo primes. 1000000007 happens to be a prime (and is often the reason it is chosen in problems by several authors). The modular arithmetic inverse of 25, modulo 1000000007 is
We arrive at this result by virtue of Fermat’s Little Theorem. Since
251000000006 = 1, modulo 1000000007 25 * 251000000005 = 1, modulo 1000000007 Thus, 251000000005 = 25-1, modulo 1000000007
Now, by using repeated squaring, we can find the modular inverse of 25 and multiply it to the numerator to find our answer.
Can be found here.
Can be found here.