自动搬运

查看原文

来自洛谷，原作者为

	E.Space 七点半的灯火 人潮将我吞没 连同我小小的歌

搬运于2025-08-24 22:47:38，当前版本为作者最后更新于2023-06-28 03:37:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里给一种不需要 dirty work 递推的方法。

求和可以改成求期望再乘方案数。

首先第一步是一样的，把连通块的贡献拆成操作的点对每个连通块里的点的贡献。记 $p(u,v,w)$ 表示操作 $u$ 之前 $u$ 的权值是 $w$ 且这一步操作时 $v$ 在那个连通块里的概率。那么答案就是

$$\sum\limits_{u=1}^n \sum\limits_{v=1}^n \sum\limits_{w=0}^{m-1} p(u,v,w) $$

容易发现，$p(u,v,w)$ 只和 $u$ 与 $v$ 的距离有关，所以设 $d$ 为 $u$ 到 $v$ 的路径上的点数（本题中我们把这个定义为两点间距离），答案可以改写成

$$\sum\limits_{d=1}^n c_d \sum\limits_{w=0}^{m-1} p(d,w) $$

其中 $c_d$ 表示路径上点数为 $d$ 的有向路径条数，$p(d,w)$ 表示一对距离为 $d$ 的点 $u,v$ 的 $p(u,v,w)$。

现在来求 $p(d,w)$。

考虑这样计算这个概率：先决定每一步操作是否在路径上，然后决定路径上的操作的位置。有贡献当且仅当路径上至少有 $dw+1$ 次操作，并且在路径上的前 $dw$ 次操作均等地分布在路径的 $d$ 个点上，并且第 $dw+1$ 次操作操作的是点 $u$。

可以发现，这三个条件中，只要满足了第一个条件，无论有多少次操作在路径上，满足后面两个条件的概率都是一样的。这个概率等于

$$\frac{(dw)!}{(w!)^dd^{dw+1}}$$

即前 $dw$ 次平均分配的方案数除以前 $dw$ 次的总方案数再乘以第 $dw+1$ 次操作位于 $u$ 的概率。

对于满足第一个条件的概率，可以考虑枚举有多少个操作在路径上。由于一次操作在路径上的概率是 $\frac{d}{n}$，所以这个概率就等于

$$\sum\limits_{i=dw+1}^m{m\choose i}\frac{d^i(n-d)^{m-i}}{n^m} $$

注意 $w$ 的取值范围是 $\left[0,\left\lfloor\frac{m-1}{d}\right\rfloor\right]$，否则就会有 $dw+1>m$。

结合上述几个部分，答案就等于

$$\sum\limits_{d=1}^n c_d \sum\limits_{w=0}^{\left\lfloor\frac{m-1}{d}\right\rfloor}\frac{(dw)!}{(w!)^dd^{dw+1}}\sum\limits_{i=dw+1}^m{m\choose i}\frac{d^i(n-d)^{m-i}}{n^m} $$

乘上最初为了算期望除掉的方案数 $n^m$，就是

$$\sum\limits_{d=1}^n c_d \sum\limits_{w=0}^{\left\lfloor\frac{m-1}{d}\right\rfloor}\frac{(dw)!}{(w!)^dd^{dw+1}}\sum\limits_{i=dw+1}^m{m\choose i}d^i(n-d)^{m-i} $$

然后就可以直接算了。

组合数和阶乘、阶乘逆元可以直接 $O(m)$ 预处理。

$d^i$ 和 $(n-d)^{m-i}$ 可以对每个 $d$ 的值 $O(m)$ 预处理，这里总复杂度是 $O(nm)$。

这样最后一个和号就可以由其右边的东西对 $i$ 做一个后缀和得到。

前两个和号的枚举是 $O(m\log n)$ 的，而计算中间那个分式的分母的逆元的时间复杂度是 $O(\log M)$ 的，其中 $M$ 为模数。

所以总复杂度是 $O(n^2+m(n+\log n\log M))$。在本题的数据范围下和标算相当。