You are not logged in. Please login at www.codechef.com to post your questions!

×

COPR16C: Editorial

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.

asked 26 Mar '16, 02:15

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 29 Mar '16, 16:15

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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