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. COMPLEXITYO(logn) per test case. AUTHOR'S SOLUTION:Author's solution can be found here. asked 26 Mar '16, 02:15
