4043 病毒

题面

内容

W 国决定攻略 Y 国的网络系统。

Y 国的网络系统由 $n$ 台编号依次为 $1,2,\dots, n$ 的服务器组成。为了防止被入侵，Y 国每天都会更改网络结构，具体的，初始时服务器之间都没有边，然后 $\forall 2\le i\le n$，第 $i$ 台服务器会从编号在 $[1,i-1]$ 内的服务器中等概率选出一个服务器，向其连一条有向边。显然，最后 Y 国的网络系统会呈现出一个以 $1$ 为根的内向树结构。

W 国早就在 Y 国的若干台服务器中种下病毒，假如有一天，存在某个点到 $1$ 的路径上出现了所有带病毒的服务器，那么 Y 国的网络系统就会崩溃。现在，Y 国请求你帮他们计算，每次更改完网络结构后，网络系统崩溃的概率。

由于 Y 国并不知道哪些服务器被种了病毒，所以他们只能对 W 国的行为进行猜测后来询问你。具体的，Y 国会询问你 $q$ 次，每次给定一个点集 $S_i$，你需要求出，假如只有 $S_i$ 内的服务器中了病毒，那每次更改完网络结构后，网络系统崩溃的概率是多少。

输入

第一行两个正整数 $n,q$。

接下来 $q$ 行：每行开头为一个正整数 $k_i$，接下来有 $k_i$ 个互不相同的在 $[1,n]$ 内的整数表示 $S_i$。

输出

输出共 $q$ 行，第 $i$ 行你需要输出当只有 $S_i$ 内的服务器中了病毒，那每天网络系统崩溃的概率，对 $998244353$ 取模。

样例1

输入

3 2
2 1 2
2 2 3

输出

1
499122177

样例2

输入

9 2
2 2 3
3 7 5 8

输出

499122177
370776474

提示

对于样例2：对于询问 $2$，可以发现如果网络系统崩溃，服务器 $8$ 必须向服务器 $7$ 连边，当服务器 $7$ 向服务器 $6$ 连边，则服务器 $6$ 必须向服务器 $5$ 连边，否则服务器 $7$ 必须向服务器 $5$ 连边，所以可能的网络结构有 $4!\cdot 8+4!\cdot5\cdot8=1152$，而 ${1152\over 8!}={1\over 35}\equiv 370776474\pmod {998244353}$。

思路

顺着边 点编号是递减的

从点i右边跳到i号点的概率永远是$\frac{1}{i}$，所以在所有点中病毒的情况下，让他们排成一条链的概率就是

给定一个$1\sim{n}$的子集$S$，询问若$i$的父亲在$[1,i-1]$中等概率生成，那么从最后一个点到一号点经过所有$S$中的节点的概率，答案对$998244353$取模。

首先，$i+1$到$i$的概率是$\frac{1}{i}$，$i+1$的父亲是$i$的概率是$\frac{1}{i}$；

$i+2$到$i$的概率是直接跳到$i$的概率加上先跳到$i+1$再跳到$i$，也就是 $\frac{1}{i+1}+\frac{1}{i+1}\times{\frac{1}{i}}=\frac{1}{i}$，通过数学归纳法得知，$i$右边的点跳到$i$的概率都是$\frac{1}{i}$。

由于每次跳这些时间是相互独立的，所以原题答案为：

$\prod_{i=1}^{m-1}{\frac{1}{x_i}}$

最后一个分数取模不要忘了求逆元。