PROBLEM LINK:

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Modular Exponentiation

PROBLEM:

String a to be strictly greater than String b (both are of same length) when each character of a is strictly greater than corresponding character in b.

For the string length l, you have to calculate how many pairs (x, y) exist such that string x is strictly greater than string y.

EXPLANATION:

Consider the case when the lenth of the string is l==1. Here the answer is 325 because the number of pairs

with a as first part are b, c, d, e,.......x, y, z i.e. 25 in number

with b as the first part are c, d, e, f, .......x, y, z i.e. 24 in number. and so on.

Total number of required pairs = $\sum_{i=0}^{25}{i}$ = $\frac{25.26}{2}$ = 325

So let us generalise the formula for length l==n

Total number of required pairs = $\sum_{i_1=0}^{25}{\sum_{i_2=0}^{25} \cdots \sum_{i_n=0}^{25} i_1.i_2 \cdots i_n}$ = $\sum_{i_1=0}^{25}{i_1} . \sum_{i_2=0}^{25}{i_2} \cdots \sum_{i_n=0}^{25}{i_n}$ = 325^n

Hence, we just need to find 325^n modulo (10^9 + 7), which can be done easily using modular exponentiation.

COMPLEXITY

O(logn) per test case.

AUTHOR'S SOLUTION:

Author's solution can be found here.