JUNONGF - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

PREREQUISITES

Math, Repeated Squaring, Fermat’s Little Theorem

PROBLEM

You are given a N dimensional hyper rectangle. You have to fill each cell in the hyper rectangle with a value between 0 and V-1, inclusive, such that the sum of all the values in each 1-dimensional slice of the hyper rectangle is divisible by V, which is also given.

Find the number of ways of filling the cells with the values.

QUICK EXPLANATION

Let the dimensions of the hyper rectangle be given in an array D = { D1, D2, … DN }.

Assume we fill the each of the following cells of the hyper rectangle with any arbitrary value from 0 to V-1 of our choosing

  • Fill { x1, x2, … xN } iff
    • x1 < D1 AND
    • x2 < D2 AND
    • so on…

The rest of the cells that have not been filled can only be filled by singular values that satisfy the divisibility constraint.

Take for example a hyper-rectangle { 4, 4, 3 } and V = 10. Suppose we fill all the cells as described above arbitrarily. There are of course 103*3*2 ways of filling them. Now, when we take any slice of this hyper-rectangle, we find that

  • Either the cell is filled by a value of our choosing
  • The value of the cell is being forced by some or the other 1-dimensional slice

All except one value in each slice will be pre-filled or forced, and the last value is of course being forced by the constraint that the sum of all the values in this slice must be divisible by V.

Thus, the answer for each case is going to be

V(D1-1)(D2-1)…(DN-1)

EXPLANATION

V is a 64-bit integer. But we want to find the result modulo 1000000007. Thus, we can instantly change V to the remainder modulo 1000000007.

Given that each of the dimensions are 64-bit integers, it is obvious that the exponent of V for the answer is potentially very large. It is potentially a 6400-bit integer. Repeated squaring to find the result of V6400-bit-integer will take 6400 iterations. This is too many iterations per test case.

We require Fermat’s Little Theorem to solve the problem now.

ap-1 = 1 modulo p

for some prime p

We know that 1000000007 is prime. Thus we can find

T = (D1 - 1)(D2 - 1) ... (DN - 1) modulo 1000000006

and find VT modulo 1000000007.

There is one edge case that deserves special mention. V modulo 1000000007 may or may not be 0. If it is not 0, then we have no problems. But if it is 0 there is a special case that should be carefully handled. This is the case where one or more dimension is equal to 1. In this case, all the values in the hyper rectangle must be 0. This is because every cell is a single dimensional slice in a dimension that is equal to 1. Thus the answer in that case should be 1, instead of 0 (meaning the answer is actually 1, and not a multiple of 1000000007).

Of course, as evil as the setter and the tester are, there is no shortage of this case among the judge test cases.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

Any idea on why this problem is in the medium section in the practice arena?? The problem is tagged easy, here.

3

@admin: testers solution is pointing to some other problem ? It is not even reading the complete input!

4

On it.

If you’re curious what problem the tester’s solution is trying to solve, it happens to be the solution to a very early version of the problem.

The input format was changed to improve the problem and hence this solution lost relevance. It seems the wrong solution got selected for upload. Will ask them to upload the correct version.

5

The official classification had not been done when the editorial was finished.

Changed the tag to medium.

6

@all @gamabunta
Hey
I could not understand the problem.
Basically I am not able to analyze/imagine the problem statement.
So any hint or explanation would be highly appreciated and welcomed.
Thanks !!!

7

anyone ???