CF1574F Occurrences

数组 $a$ 的从下标 $l$ 到下标 $r$ 的子数组是指 $[a_l, a_{l+1}, \dots, a_{r}]$。数组 $b$ 在数组 $a$ 中出现的次数，指的是 $a$ 的子数组中等于 $b$ 的子数组的个数。 现在给定 $n$ 个数组 $A_1, A_2, \dots, A_n$，这些数组的元素都是 $1$ 到 $k$ 之间的整数。你需要构造一个长度为 $m$ 的数组 $a$，其中每个元素也是 $1$ 到 $k$ 之间的整数。要求对于每一个给定的子数组 $A_i$，$A_i$ 在 $a$ 中出现的次数不少于 $A_i$ 的每一个非空子数组在 $a$ 中出现的次数。注意，如果 $A_i$ 在 $a$ 中没有出现，并且 $A_i$ 的所有子数组在 $a$ 中也都没有出现，那么这个条件对于 $A_i$ 依然成立。 你的任务是计算可以构造的不同数组 $a$ 的数量，并对 $998244353$ 取模后输出。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 3 \times 10^5$），分别表示给定数组的数量、所需数组 $a$ 的长度以及数组元素的最大值。 接下来有 $n$ 行，每行描述一个数组 $A_i$。第 $i$ 行的第一个整数 $c_i$（$1 \le c_i \le m$）表示 $A_i$ 的长度，接下来有 $c_i$ 个整数，分别为 $A_i$ 的元素，这些元素的取值范围为 $1$ 到 $k$。 输入还保证：$\sum\limits_{i=1}^n c_i \le 3 \times 10^5$，即所有给定数组的元素总数不超过 $3 \times 10^5$。

输出一个整数，表示可以构造的不同数组 $a$ 的数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译