CF2169F Subsequence Problem

给定三个整数 $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$ 取模。

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