P13694 [CEOI 2025] Splits
题目描述
对于一个长度为 $n$ 的排列 $p = p[0], p[1], p[2], \ldots, p[n - 1]$（包含数字 $1, 2, 3, \ldots, n$ 的一个全排列），我们定义**分割排列**（split）为一个排列 $q$，它可以通过以下过程得到：
1. 选择两个数集
$A = i_1, i_2, \ldots, i_k$
$B = j_1, j_2, \ldots, j_l$
满足：
- $A \cap B = \emptyset$
- $A \cup B = \{0, 1, 2, \ldots, n - 1\}$
- $i_1 < i_2 < \ldots < i_k$
- $j_1 < j_2 < \ldots < j_l$
2. 将 $q$ 定义为：
$$
q = p[i_1]\, p[i_2] \ldots p[i_k]\, p[j_1]\, p[j_2] \ldots p[j_l]
$$
进一步，我们定义 $S(p)$ 为排列 $p$ 的所有分割排列的集合。
现在，给定一个整数 $n$ 和一个集合 $T$，其中包含 $m$ 个长度为 $n$ 的排列。要求统计有多少个长度为 $n$ 的排列 $p$ 满足 $T \subseteq S(p)$。由于答案可能很大，请将结果对 $998\,244\,353$ 取模。
### 实现细节
你需要实现以下函数：
```cpp
int solve(int n, int m, std::vector& splits);
```
* $n$：排列的长度
* $m$：给定的分割排列数量
* `splits`：包含 $m$ 个两两不同的排列，表示集合 $T$，该集合是某个 $p$ 的 $S(p)$ 的子集
该过程应返回满足条件的排列数量，结果对 $998\,244\,353$ 取模。该过程在每个测试用例中仅调用一次。
输入格式
无
输出格式
无
说明/提示
### 样例解释 1
考虑以下调用：
```cpp
solve(3, 2, {{1, 2, 3}, {2, 1, 3}})
```
在此例中，排列 $p$ 的长度为 $3$，给定的分割排列有：
* $123$
* $213$
只有以下 $4$ 个排列 $p$ 可以同时生成这两个分割排列：
* $123$
* $132$
* $213$
* $231$
因此答案为 $4$。
### 数据范围
* $1 \leq n \leq 300$
* $1 \leq m \leq 300$
### 子任务
1. （6 分）$m = 1$
2. （7 分）$1 \leq n, m \leq 10$
3. （17 分）$1 \leq n, m \leq 18$
4. （17 分）$1 \leq n \leq 30,\ 1 \leq m \leq 15$
5. （16 分）$1 \leq n, m \leq 90$
6. （16 分）$1 \leq n \leq 300,\ 1 \leq m \leq 15$
7. （21 分）无额外限制
---
翻译由 ChatGPT-5 完成