题解 - T168872 既见君子

· · 题解

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

数据范围：n\le 20

解答：

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

可以用朴素的 $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$ 分。欢迎大神写出一些小常数的代码，然后把这题加强一下。）