TAPALIN - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math, Matrix Exponentiation

PROBLEM

Find the number of palindromic strings that can be made of length N, or less.

QUICK EXPLANATION

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 )

EXPLANATION

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

251000000005

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.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

8 Likes
2

What I figured out is this recurrence : T(n)=27 * T(n-2)-26 * T(n-4)
and then solved using matrix exponentiation…NO MULTIPLICATIVE INVERSE INVOLOVED !! and I was expecting my solution to fail! suprisingly it got AC :slight_smile:
Here’s LINK to my solution.

6 Likes
3

Nice explanation… I was able to find the formula for the sum of consecutive powers but unfortunately got stuck in some annoying logical errors… It’s nice to find another problem that requires modular multiplicative inverse, I think it’s time for me to finally try and understand it, nice problem btw :slight_smile:

1 Like
4

I spent so much time with this one, that I had no enough time for TABUS :frowning:

To calculate sum(a, n)

sum( a, k ) = a + a^2 + a^3 + ... + a^k;

I used another approach:

sum( a, 2k ) = sum( a, k ) * ( 1 + a^k )

for example:

sum( a, 6 ) = a + a^2 + a^3 + a^4 + a^5 + a^6
            = a + a^2 + a^3 + a^3 * ( a + a^2 + a^3 )
            = (a + a^2 + a^3 + a^3) * ( 1 + a^3 )
            = sum( a, 3 ) * ( 1 + a^3 )

and simply

sum( 2k+1 ) = sum( 2k ) + a^(2k+1)
4 Likes
5

1)I did same thing.I got the answer for n=100,Still got Wrong answer!!
Here is my solution!!
http://www.codechef.com/viewsolution/1963809
Can someone tell me the mistake!!
2)I also used the above formula of GP …I didnt understand y can’t we simple take modulo and then finally divide by 25??
Thanx in advance!!

6

The answer for your second question is:

( 10^9 + 10 / 25 ) % MOD = 1000000000

while

( ( 10^9 + 10 ) % MOD ) / 25 = 0
1 Like
7

your solution complexity is O(T*N) and that’s really slow…

1 Like
8

for calculating modular multiplicative inverse either you can be smart or can visit http://www.cs.princeton.edu/~dsri/modular-inversion.html and put n=25 and M=10^9 !

1 Like
9

In the solution,i found that adding “mod” while computing answer for odd cases gives correct answer…i know that if i not do that it gives negative result but since in the question we were asked for finding modulo of ans …doing that gives incorrect answer…can anyone plz explain why this is happening??Also i didn’t get how to compute (a-b)%n…

1 Like
10

I know I little bit of modulo arithmetic, but I completely I don’t understand how division by 25 is equivalent to multiplying by its inverse. I mean division isn’t even defined in modular arithmetic.

Please Explain.

11

Great explanation. I can say I actually learned something valuable from this editorial.

I saw in the setter’s solution he used matrix exponentiation. However, the M matrix I see here:

        |26   26|
        | 0    1|

is different than the one he used in his code:

    |26    0|
    | 1    1|

It made me struggle a bit.I found another recurrence:

      f(n) = 26f(n - 2) + 52
      f(n+1) = 26f(n - 1) + 52

and used as M:

|26  52| 
|0    1|

Here’s my code:

http://www.codechef.com/viewsolution/1967153

1 Like
12

I don’t understand. Can’t I divide by 25 instead of multiplying multiplicative inverse of 25. I think result would be the same. Wouldn’t it?

13

@dwatson_bynes : Not you can’t . Suppose you are calculating x/35 mod 15 . Let x be 140. If you are not keeping the actual value of “x” , but only storing it mod 15 , then you will have 5 , and when you divide by 35 you will get 0 or a decimal value . However 140/35 = 4 , which is = 4 with respect to mod 15 .

14

okay, thank you. That cleared my doubt.

15

I did it by taking the modulo (25*1000000007) instead of modulo 1000000007.
That way you get a number which is modulo of 1000000007 and divisible by 25.
yappeee…

16

I did the above question as follows http://ideone.com/yUlTvx ,
but I am unable to find the solution.PLEASE HELP…

17

link text

I think this is a unique method quite different from other implementations that people did.

If you want to learn matrix exponentiation u gotta try this thing.

http://www.codechef.com/viewsolution/7286572

18

It might be nice to have a lower N test case that will usually work with a straight addition of powers in the time available - say as a 10% solve.

Calculating modular inverse through the extended Euclidean algorithm would remove the dependence on the modulus being prime.