Educational Codeforces Round 109 Assimilation IV Solution(Java/C++)

Solution:

To get the expected number, we need calculate the total number of points can be conquered in all permutation.
To get the total number of points, we calculate it point by point. We calculate the number of permutations which will conquer this point.

Then we will find that it is hard to find out the number which will conquer this point. So, we calculate the number of permutations which will not conquer this point.

Consider the 5th point in the sample data. The distances between this point to each city are 4, 2, 3.
The 1st city cannot conquer this point at all. So, 1st city can be put in any position of the permutation.
For the 2nd city, if and only if 2nd city is the last city of the permutation, the point is not conquered.
For the 3rd city, if and only if 3rd city is the last or the second last city of the permutation, the point is not conquered.

But consider the 2nd and 3rd cities. We found that: because the 2nd only can be the last city. So, 3rd city only can choose second last one.
Then we know that, the city is nearer to the point, then it is harder to not conquer the point. Also, it will affect the next city.

Now the solution is obvious. For any point j, we calculate the number of possibilities which is not conquer this point for each of the cities one by one from near to far. So for i-th city, the number of possibilities is: $\min(d_{i,j}-1-i,n-i)$.
(Because it already assigned nearer cities to the permutation. So, need exclude these positions from current possibilities.)

Now we got the number of permutations which will conquer this point. The sum of this is the numerator.
And then the denominator is the modular multiplicative inverse of all permutations. We can get it by Fermat's little theorem.

Code:

Tips: $20!$ is not exceed $2^{64}$. So, do not get the modular of the number of all permutations and the permutations which do not conquer the point. Otherwise, the difference between these two numbers may be negative.

Java

C++