P9357 题解

· · 题解

这里给一种不需要 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) 预处理。

这样最后一个和号就可以由其右边的东西对 $i$ 做一个后缀和得到。 前两个和号的枚举是 $O(m\log n)$ 的，而计算中间那个分式的分母的逆元的时间复杂度是 $O(\log M)$ 的，其中 $M$ 为模数。 所以总复杂度是 $O(n^2+m(n+\log n\log M))$。在本题的数据范围下和标算相当。