PROBLEM LINK:
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.