自动搬运

查看原文

来自洛谷，原作者为

	樱初音斗橡皮 （只读）真是个有趣的世界呢

搬运于2025-08-24 22:29:51，当前版本为作者最后更新于2021-02-19 19:34:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意：给定 $n$ 点 $m$ 边无向连通图，随机一个生成树，求 $1$ 到 $n$ 的简单路径经过点 $z$ 的概率。对 $998244353$ 取模。

数据范围：$n\le 20$

解答：

首先很显然生成树个数可以 $O(n^3)$ 求出，因此求出 $1\sim n$ 经过 $z$ 的总生成树个数即可。

$f_{i,S}$ 表示从 $1$ 开始经过点集 $S$ 到达 $i$ 的路径数，$g_{i,S}$ 表示从 $n$ 开始经过点集 $S$ 到达 $i$ 的路径数，$h_{S}$ 表示将 $S$ 之外的点全部缩成一个点之后的生成树个数。则最终答案为 $\displaystyle Ans=\sum_{S_1\cap S_2=\{z\}}f_{z,S_1}\cdot g_{z,S_2}\cdot h_{S-S_1-S_2}$。

可以用朴素的 $O(3^n)$ 算法或 $O(2^n\cdot n^2)$ 子集卷积实现。

$f$ 的计算方式：$f_{i,S}$：$f_{1,\{1\}}=1$；$f_{i,S}=[i\in S]\sum_{j\in S}e(j,i)\cdot f_{j,S-\{i\}}$。$g$ 的计算方式类似。

现在我们面临了一个问题：对每一个 $S\subset \{1,2,\ldots n\}$ 求出 $h_S$。

朴素实现：$O(2^n\cdot n^3)$ 高斯消元。

精细实现：优化高斯消元的过程。考虑新加入一个点对行列式的改变其实是加入一行一列，在高斯消元的过程中记录行变换的步骤（$O(n^2)$），则每次加入一行一列都至多多出 $O(n)$ 次行变换，可以 $O(n^2)$ 更新。这样即可用 $h_S$ 推出 $h_{S\cup \{i\}}$ 的答案。

时间复杂度 $O(2^n\cdot n^2)$。

（实际上由于常数原因，后者不一定跑得过前者，而 $O(2^n\cdot n^3)$ 的算法也可以通过，带 $3^n$ 的算法能拿 $80$ 分。欢迎大神写出一些小常数的代码，然后把这题加强一下。）