THREEDIF - Editorial

anton_lunyov · January 15, 2013, 3:00pm

PROBLEM LINK:

Practice
Contest

Author: Anton Lunyov
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Rule of product in combinatorics, Modulo operation

PROBLEM:

You are given 3 positive integers N₁, N₂, N₃ up to 10¹⁸ and need to count the number of triples (X₁, X₂, X₃) such that 1 ≤ X_i ≤ N_i for i = 1, 2, 3. You should output the answer modulo 10⁹ + 7.

QUICK EXPLANATION:

By sorting input numbers we can assume that N₁ ≤ N₂ ≤ N₃. Then the answer is N₁ * (N₂ − 1) * (N₃ − 2). Watch out for integer overflows during calculation of this number modulo 10⁹ + 7.

EXPLANATION:

If we sort numbers N₁, N₂, N₃ the answer remains the same. Hence let’s assume that N₁ ≤ N₂ ≤ N₃. Then for X₁ we have N₁ choices, for X₂ we have N₂ − 1 choices and for X₃ we have N₃ − 2 choices. Indeed:

X₁ can be any number from 1 to N₁, inclusive. There are N₁ such numbers
X₂ can be any number from 1 to N₂, inclusive, which is not equal to X₁. Since X₁ ≤ N₁ ≤ N₂, there are N₂ − 1 such numbers (numbers from 1 to N₂, inclusive, with excluded X₁). Clearly, if N₁ = N₂ = 1 then the answer is zero since the only choice for X₁ and for X₂ is 1, so any such triple will have equal numbers.
Finally, if N₃ ≥ 2 then X₃ can be any number from 1 to N₃, inclusive, which is not equal to X₁ and X₂. Since X₁ ≤ N₁ ≤ N₃, X₂ ≤ N₂ ≤ N₃ and X₁ ≠ X₂, there are N₃ − 2 such numbers (numbers from 1 to N₃, inclusive, with excluded X₁ and X₂).

Now using rule of product in combinatorics we get that the answer is simply the product of N₁, N₂ − 1 and N₃ − 2 as mentioned above. Note that when N₂ = 1 this formula also works so we don’t need to handle this case separately.

Probably the trickiest part is to output the answer modulo M = 10⁹ + 7 having numbers N_i up to 10¹⁸. There are several things you should notice in order to get AC:

You should use 64-bit integer type to store and input numbers N_i.
When you want to multiply two numbers up to 10¹⁸ modulo 10⁹ + 7 you should at first take them modulo 10⁹ + 7 and then do the multiplication using 64-bit integer type. Otherwise the result will be wrong due to overflow. Even such code is wrong
A % M * B % M
since you will multiply numbers A M** and **B** at the second step and this will lead to overflow (**A M is about 1e9 and B is about 1e18, so their product is about 1e27 which does not fit in 64-bit integer type). Such overflow will occur on almost every random test.
Another common mistake is to do like that
A = N1 % M
B = (N2 - 1) % M
C = (N3 - 2) % M
ans = A * B * C % M
Here at the final step you multiply three numbers up to about 1e9. Their product could be up to 1e27 which does not fit in 64-bit signed integer. Therefore integer overflow occurs. The correct code would be
ans = A * B % M * C % M
Here we take the product A * B modulo M so it becomes smaller than M and at the final step you multiply two numbers up to about 1e9. Their product is up to about 1e18 and fits in 64-bit integer type.
You can’t replace numbers N_i by their residues modulo 10⁹ + 7 before sorting. Indeed, the order of numbers can change after that and you get completely another number as the answer. The reference test is: 2 3 1000000008. Actually it happens often on any large random test.
If after sorting you replace numbers N_i by their residues modulo 10⁹ + 7 and then calculate the answer as
ans = N1 * (N2 - 1) % M * (N3 - 2) % M
then your answer could be negative in the end. The reference test is: 1 2 1000000008.
Hence if you are using this method make the check
if ans < 0 then ans = ans + M
after that.
As mentioned one of the ways how to do all properly is to calculate answer as follows
ans = (N1 % M) * ((N2 - 1) % M) % M * ((N3 - 2) % M) % M
Note that at first sight this way also could lead to negative answer. But this does not happen here. See comments in tester’s solution for explanation.

Actually, it is easy to see that this solution could be generalized to any number of variables instead of 3. Namely, if we have numbers N[0], N[1], …, N[K-1] and want to count the number of arrays (X[0], X[1], …, X[K-1]) such that 1 ≤ X[i] ≤ N[i] for i = 0, 1, …, K-1, and all X[i] are different, then after sorting numbers N[i] the answer will be the product of N[i] − i for i = 0, 1, …, K-1. See tester’s solution as a reference.

ALTERNATIVE SOLUTION:

The problem could be solved using inclusion-exclusion principle. The formula for the answer in this case is
N₁ * N₂ * N₃ − min{N₁, N₂} * N₃ − min{N₂, N₃} * N₁ − min{N₃, N₁} * N₂ + 2 * min{N₁, N₂, N₃}.
See author’s solution as a reference. It also contains explanatory comments to this formula.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.