T24 - Editorial

general
,
1

PROBLEM LINK:

[Contest] T24

Author: Jitendra Yadav

DIFFICULTY:

SIMPLE

PROBLEM:

You are given N number of questions and K are the number of choices you get for each question. You have to find the sum of total number of players who has attempted ith question. The answer can be very large therefore, you are required to print (sum of total number of players) % 10^9+7.

EXPLANATION:

Suppose you are given 3 questions and each question has 3 choices. So, you need to find the players for each question. For 1st question, 3^3=27 (there are 3 choices each for 3 questions) players played then for 2nd question, 3^2 = 9 (there are 3 choices each for 2 questions left) players played and finally for 3rd question, 3^1 = 3 (there are 3 choices each for 1 question left) players played.

So, the sum of total players played is 27+9+3=39.

Now you need to calculate the following operation i.e. 39%10^9+7 which will give you 39 as the output.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here

2

@innerve - we can’t access your solution. It’s in some kind of admin area. Why don’t you resubmit it through the normal (now practice) submission process and give us that link?

Also: an editorial should talk about the techniques needed to solve the problem, rather than just presenting the problem over again. In this case the formula for the sum of a geometric series would be a useful discussion:

1+ a + a^2+\cdots a^n = \frac{a^{n+1}-1}{a-1}

… which then also means that modular inverses may be required knowledge, to allow that division while keeping everything \bmod 1000000007.

I’ll also just note that imaginary scheme will run out of particles in the visible universe to represent the players in the first round for relatively low values of K, whenever N>1.