### PROBLEM LINK:

**Author:** Vaibhav Tulsyan

**Tester:** Aditya Paliwal

**Editorialist:** Aswin Ashok

### DIFFICULTY:

EASY

### PREREQUISITES:

### PROBLEM:

A short and concise description of the problem statement.

Bob has a string **(S)**, which is initially empty. In one operation, he can select a

lowercase character (a-z) uniformly at random and appends it to S. He then

evaluates whether S is a palindrome or not; if it is, he gets 1 point.

Given that Bob performs **N** operations in total, find the expected no. of points Bob gets.

### EXPLANATION:

Given an empty string, Bob randomly picks a character from ‘a’ to ‘z’

and appends to the string and every time he appends he checks if the resultant

string is a palindrome, if yes he get one point for that append operation. Bob does

n such append operations and we are asked to find the expected value of the total

number of points he gets. We have to find the answer modulo 10^9 + 7.

### SOLUTION:

It is the sum of expected number of palindromes of **length i**, **for i=1 to n**.

We can get the probability of getting a palindrome of length **i** by fixing the **first i/2**

characters and let the **second i/2** characters be the mirror image of the first. For

example: A string of length 4 will be palindromic if we fix its first two characters

and let the next two be the mirror of the first two and for a String of length 5 we

can fix the first three characters and let the last two characters be the mirror of

first two. **This works out to be** 26^{ceil (i/2)}/26^i **which is** f(i)= 1/26^{floor(i/2)}.

This is because ceil(i/2) + floor(i/2) = i (for all integers)

The final answer is \sum_{i=1}^{i=n} f(i)

**This becomes:**

1 + 1/26 + 1/26 + 1/26^2 + 1/26^2 + …..+1/26^{floor(n/2}

We can notice same terms repeating so we can re write the series

1 + 2(1/26 + 1/26^2 + 1/26^3 + . . . + 1/26^{floor(n/2)}) **if n is odd**

1 + 2(1/26 + 1/26^2 + 1/26^3 + . . . + 1/26^{floor(n/2)}) - 1/26^{(n/2)} **if n is even**

Since **n** is very large we cannot evaluate every term. We can notice that (1/26 +
1/26^2 + .. ) is in GP so we can use sum of GP formula and Modular Multiplicative

inverse to get the final answer.

### TIME COMPLEXITY

To find sum of GP we have to find Modular Multiplicative inverse of the

denominator in the sum of GP formula, which can be found out using Modular

Exponentiation and the time taken for it is O(logn) and last term if n is even can

also be found out it O(logn), Multiplication and addition can be performed in O(1)

so it can be done in O(logn). Since there are t cases per file the overall complexity

is O(tlogn).

### SOLUTIONS LINK:

Tester’s solution can be found here.

Editorialist’s solution can be found here.