PROBLEM LINK:
Author: Mugurel Ionut Andreica
Tester: Mahbub
Editorialist: Jingbo Shang
DIFFICULTY:
Hard
PREREQUISITES:
Combination, Inclusion–exclusion principle, Euler’s theorem
PROBLEM:
Find out how many distinct integer point sets are there in N dimension with diameter D. Diameter is defined as the maximum range of the point set among N dimensions. And two point sets are treated as same if and only if they can be coincided after translation (adding some offset).
EXPLANATION:
First of all, we need to make our goal clearer. Because of the restriction of D, we can assume all points are in the cube of [0, D]^N. And, to eliminate the duplicated point set, we can force that the zeros in all dimensions should be reached by at least one point in the chosen point set (can be several points to cover different dimensions). Further, to make sure the diameter is exactly D, we need there exists one dimension, whose D is reached by some point.
After writing this clearer goal, you may find it is still complicate. Let’s see a simpler version:
Replace the restriction of diameter = D of diameter <= D.
If we can solve this simpler version, the original problem can be solved too – using the answer of <= D minus the answer of <= D - 1. Therefore, let’s focus on the simpler one:
How many point sets are there, satisfying (1) points are in [0, D]^N; (2) zeros in all dimensions are reached by some point (can be several points to cover different dimensions).
Intuitively, this problem can be solved by Inclusion–exclusion principle. Follow the same notations in wiki, let’s define Ai as the event of the zero of i-th dimension has NOT been reached. And then, the number of point sets that zeros from at least k dimensions have NOT been reached equals:
C(N, k) * 2^(D^k * (D + 1)^(N-k))
We can prepare the C(N, k), which is the combination number, in O(N^2) time. Via Euler’s Theorem, we can calculate D^k * (D + 1)^(N-k) module phi(10^9 + 7) (equals to 10^9 + 6, denote as PHI).
Therefore, we can calculate the summation of the following term from k = 0 to k = N in O(NlogPHI) time. The log comes from the fast power module.
(-1)^k * C(N, k) * 2^(D^k * (D+1)^(N-k))
In summary, we can solve this problem in O(N^2 + T * N log PHI) time, T is the number of test cases. Furthermore, if we calculate the combination number by factorials (Buffer all factorials in an array. The division can be handled in O(log PHI) time since the 10^9+7 is a prime), the time complexity can be controlled within O(T * N log PHI).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
