1009. I. Gather

题目描述

有 (n) 个互不相同的字符，用 $\{1, 2,\cdots n\}$ 编号。

考虑一棵点集为 ({1,2,\ldots,n})、以点 (1) 为根的有标号树。 初始时，点 (i) 上放有一个仅包含一个字符 (i) 的字符串。

一次「聚拢」操作按照以下方式进行：

1. 选择一个点 (u)；
2. 将点 (u) 以及所有与 (u) 相邻的点上的非空字符串，按照任意顺序拼接成一个新字符串；
3. 将新字符串放在点 (u) 上，并清空所有与 (u) 相邻的点上的字符串为空串。

操作序列还需要满足：

• 第一次操作必须选择根 (1)；
• 除第一次操作外，每次参与拼接的字符串中，至少有一个字符串的长度不小于 (2)；
• 最终某个点上需要得到一个长度为 (n) 的字符串。

对于一棵树 (T)，记 (F(T)) 为所有合法操作序列能够得到的字典序最小字符串。

现在给定一个 (1,2,\ldots,n) 的排列 (p_1,p_2,\ldots,p_n)，求有多少棵有标号树 (T) 满足

根始终固定为点 (1)。两棵树只要无向边集不同，就被认为是不同的树。

答案对 (998244353) 取模。

样例解释

对于第一组数据，两棵合法的树的边集分别为：

{(1,2),(1,3)}
{(1,2),(2,3)}

对于第二组数据，唯一合法的树的边集为：

{(1,3),(2,3)}

数据范围

• (1\leq T\leq10)；
• (2\leq n\leq200)；
• 对于所有测试数据，(n) 之和不超过 (400)；
• (p_1,p_2,\ldots,p_n) 是 (1,2,\ldots,n) 的排列。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 (n)；
• 第二行包含 (n) 个整数 (p_1,p_2,\ldots,p_n)，保证它们构成 (1,2,\ldots,n) 的排列。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的树的数量对 (998244353) 取模后的结果。

样例输入

3
3
1 2 3
3
1 3 2
4
1 3 4 2

样例输出

2
1
3

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1009