随机漫游
题目描述
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(\mathrm{mod}\ 998244353)$,
且$0\leq r < 998244353$,可以证明这样的 $r$是唯一的
输入输出样例
输入样例 #1
3 2
1 2
2 3
3
2 1 2 1
3 1 2 3 1
1 3 1
输出样例 #1
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}$