← 返回题目
题库练习 Subsequence Problem
← 上一题 下一题 →

A16731 | Subsequence Problem

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

输入输出样例

输入 #1
4 5 3
1 1 2
4
1
4 3
输出 #1
2
输入 #2
3 5 2
1 1
5
2
输出 #2
13
输入 #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
C++ 编辑器
输入
输出