PROBLEM LINKSDIFFICULTYMEDIUM PREREQUISITESMath, Repeated Squaring, Fermat's Little Theorem PROBLEMYou are given a N dimensional hyper rectangle. You have to fill each cell in the hyper rectangle with a value between 0 and V1, inclusive, such that the sum of all the values in each 1dimensional 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 EXPLANATIONLet the dimensions of the hyper rectangle be given in an array D = { D_{1}, D_{2}, ... D_{N} }. Assume we fill the each of the following cells of the hyper rectangle with any arbitrary value from 0 to V1 of our choosing
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 hyperrectangle { 4, 4, 3 } and V = 10. Suppose we fill all the cells as described above arbitrarily. There are of course 10^{3*3*2} ways of filling them. Now, when we take any slice of this hyperrectangle, we find that
All except one value in each slice will be prefilled 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^{(D11)(D21)...(DN1)} EXPLANATIONV is a 64bit 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 64bit integers, it is obvious that the exponent of V for the answer is potentially very large. It is potentially a 6400bit integer. Repeated squaring to find the result of V^{6400bitinteger} will take 6400 iterations. This is too many iterations per test case. We require Fermat's Little Theorem to solve the problem now. a^{p1} = 1 modulo p for some prime p We know that 1000000007 is prime. Thus we can find T = (D_{1}  1)(D_{2}  1) ... (D_{N}  1) modulo 1000000006 and find V^{T} 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 14 May '13, 15:39

@admin: testers solution is pointing to some other problem ? It is not even reading the complete input! answered 14 May '13, 17:24
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.
(14 May '13, 18:41)

@all @gamabunta
answered 03 Jun '13, 21:48
