×

# COPR16C: Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

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.

6★likecs
3.7k2380
accept rate: 9%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×1,646
×593
×32
×1

question asked: 26 Mar '16, 02:15

question was seen: 489 times

last updated: 29 Mar '16, 16:15