P4321 随机漫游

题目描述

H 国有 $N$ 个城市。

在接下来的 $M$ 天，小 c 都会去找小 w，但是小 c 不知道小 w 的具体位置，所以小 c 决定每次随机找一条路走，直到遇到了小 w 为止。

小 c 知道小 w 只有可能是在 $c_{1}, c_{2} . . c_{n}$ 这 $n$ 个城市中的一个，小 c 想知道在最坏情况下，小 c 遇到小 w 期望要经过多少条道路。

H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市。

任何时候，H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$ 。

输入第 1 行一个正整数 $N, E$ ，分别表示 H 国的城市数与边的数量

输入第 2 行至第 $E + 1$ 行，每行两个正整数 $u, v$ ，分别表示城市 $u$ 到城市 $v$ 有一条道路

输入第 $E + 2$ 行一个正整数 $M$

输入第 $E + 3$ 行至第 $E + M + 2$ 行每行 $n + 2$ 个正整数，第一个正整数为 $n$ ，接下来 $n$ 个互不相同的正整数 $c_{i}$ ，最后一个正整数 $s$ 表示小 c 所在的城市

输出共 $M$ 行，每行一个正整数 $r$ 表示答案

如果你计算出来的期望为 $\frac{q}{p}$ ，其中 $p, q$ 互质，那么你输出的 $r$ 满足 $r \times p \equiv q (\mod 998244353)$ ，且 $0 \leq r < 998244353$ ，可以证明这样的 $r$ 是唯一的

1
2
3

1
4
4

$H$ 国的道路构成一条链，所以最坏情况下就是小 w 在深度最大的点上(以小 c 所在的城市为根)

对于第一天，小 c 所在的城市为 1，深度最大的点为 2，城市 1 只能到达城市 2，期望经过 1 条道路到达

对于第二天，小 c 所在的城市为 1，深度最大的点为 3，计算的期望经过 4 条道路到达

第三天同第二天

最坏情况也就是说经过所有 $n$ 个可能的城市至少一遍

subtask1 : 10分， $N = 4, M = 12$

subtask2 : 15分， $N = 10, M = 100000$

subtask3 : 15分， $N = 18, M = 1$

subtask4 : 10分， $N = 18, M = 99995$ ，图是一条链

subtask5 : 10分， $N = 18, M = 99996$ ，所有的 $s$ 都相同

subtask6 : 15分， $N = 18, M = 99997$ ， $E = N - 1$

subtask7 : 15分， $N = 18, M = 99998$ ，所有的 $s$ 都相同

subtask8 : 10分， $N = 18, M = 99999$

对于所有数据 : $1 \leq N \leq 18, 1 \leq M \leq 100000, 1 \leq E \leq \frac{N (N - 1)}{2}$ 。

状态转移原则：求概率正向转移，求期望逆向转移。

设 $f (S, x)$ 表示已经遍历过了 $S$ 集合，当前在点 $x$ 时，要遍历完整个图的期望步数。那么对于每个询问的点集 $C$ ， $f ((V ∖ C) \cup {s}, s)$ 就是答案，因为我们从 $V ∖ C$ 集合到全部走完刚好把询问的点全部走了一次。

状态转移方程很直观：

f (S, u) = \frac{1}{{deg}_{u}} \times \sum_{(u, v) \in E} f (S \cup {v}, v) + 1

显然状态之间的依赖关系不是 DAG，需要使用高斯消元代替一般的 DP。状态总共有 $n 2^{n}$ 个，高斯消元的复杂度为 $O ((n 2^{n})^{3})$ 显然需要优化。

观察上式，可以发现 $S$ 一定是被包含在 $S \cup {v}$ 里的，也就是说一个状态只能由一个点集不小于该状态的状态转移而来。

考虑对状态进行分层，层间是单向依赖，层内依赖关系才可能成环。从大到小在每个点集 $S$ 内部分别进行高斯消元，复杂度 $O (n^{3} 2^{n})$ 。