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

题意

你有n个城市。每回合你要选一个城市来修纪念碑。一开始纪念碑的辐射范围是1，此后每回合辐射范围加一。总共修n个纪念碑。

现在有m个点，给你每个点到每个城市的距离。

对于每一种修法的排列，分数就是至少被一个城市的纪念碑辐射到的。问所有排列的分数期望。

题解

把点拆开来看。我们考量每个点能被多少种排列覆盖。
我们立刻发现，要计算被多少种排列覆盖其实有一定的困难，于是我们考虑有多少种排列不会覆盖这个点。

我们考察样例中的第5个点。这个点距离三个城市的距离分别是4，2，3。
我们可以看到这个点完全不可能被第1个城市覆盖，于是第一个城市可以是在排列中的任意位置。
对于第2个城市，我们发现，当且仅当这个城市是排在最后一个的情况下，这个点不会被覆盖。
对于第3个城市，可以排在最后一位或者倒数第二位这个点不会被覆盖。

但考量第2个城市和第3个城市，我们发现，由于第2个城市只能选择最后一位，于是导致实质上第3个城市只能选择倒数第二位。
于是我们发现，距离越近的城市，想不覆盖到点的要求越严格，且会影响后面距离远的城市。

于是做法就很显然了。对于任意一个点j，我们从今到远一个一个算每一个城市在不覆盖当前点的情况下的所有可能。其对于排序后的第i个城市，其可能数为$\min(d_{i,j}-1-i,n-i)$。
（因为前面已经排了较近的点，因此剩下的选择数要减去这些点）

在我们求出了某个点不被任何城市覆盖的所有排列数之后。剩下的就只是做差求和就可以得到分子。而分母就是根据费马小定理求一个逆元的事情。

代码

小提示：$20!$并不会超过$2^{64}$。因此总可能数和不覆盖的可能数在计算过程中不要取模，否则减下来可能得到一个负数反而麻烦。

Java

C++