CFCF2169F.Subsequence Problem

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定三个整数 $n, m, k$ ，以及 $k$ 个整数数组，这些数组的长度分别为 $l_1, l_2, \dots, l_k$ 。我们用 $a_{i,j}$ 表示第 $i$ 个数组的第 $j$ 个元素。在每个数组中，所有元素互不相同（但不同数组之间的元素可以重复）。

我们称一个长度为 $k$ 的数组 $b$ 是“美丽”的，当且仅当对于每个 $i$ 从 $1$ 到 $k$ ，元素 $b_i$ 必须等于数组 $a_i$ 中的某一个元素。

我们称一个数组 $c$ 是“完美”的，当且仅当每一个“美丽”的数组 $b$ 都可以通过从 $c$ 中删除若干（可能为零）元素后、不改变剩下元素的顺序得到。换句话说， $c$ 是“完美”的，当且仅当所有可能的“美丽”数组 $b$ 都是 $c$ 的子序列。

你的任务是计算长度为 $n$ 、仅由 $1$ 到 $m$ 之间的整数组成的“完美”数组 $c$ 的总数。

第一行包含三个整数 $n, m, k$ （ $2 \le n \le 2 \cdot 10^5$ ； $5 \le m \le 10^8$ ； $2 \le k \le n$ ）。

第二行包含 $k$ 个整数 $l_1, l_2, \dots, l_k$ （ $1 \le l_i \le 5$ ）。

接下来 $k$ 行，每行 $l_i$ 个两两不同的整数 $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$ （ $1 \le a_{i,j} \le m$ ）。

输入还保证 $\sum l_i \le n$ 。

输出一个整数，表示满足条件的长度为 $n$ 且仅由 $1$ 到 $m$ 组成的“完美”数组 $c$ 的总数。结果对 $998244353$ 取模。

输入#3

200000 12345678 7
3 2 5 1 3 4 5
42 13 37
37 13
1 2 3 4 5
3
3 1 4
1 5 9 2
1 2 3 4 5

输出#3

152094503

在第一个样例中，有两个“美丽”数组： $[4, 1, 4]$ 和 $[4, 1, 3]$ 。只有两个长度为 $4$ 的数组同时包含这两个子序列： $[4, 1, 4, 3]$ 和 $[4, 1, 3, 4]$ 。

在第二个样例中，只有一个“美丽”数组 $[5, 2]$ 。有 $13$ 个长度为 $3$ 的、元素在 $1$ 到 $5$ 之间的数组，包含它作为子序列。