← 返回题目列表

Codeforces · 2187/F2

F2. Al Fine(计数版)

中文机器翻译题面 查看原题

这是问题的计数版本。版本之间的区别在于,在这个版本中,你需要找到不同公共树的数量。此外,此版本中对 $$$n$$$ 的约束较小。只有解决了该问题的所有版本,您才能破解。

圣诞节,Tortinita 和 Arietta 各得到一棵圣诞树。巧合的是,它们的树具有相同的属性:都有 $$$n+1$$$ 顶点,并以顶点 $$$0$$$ 为根。在他们给你的圣诞贺卡中,他们每个人都会在问候后附加他们的圣诞树的 DFS 订单序列。回想一下,DFS 订单序列是由以下伪代码生成的。

dfs_order = []

def dfs(v):
dfs_order.append(v)
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)

dfs(root)

设 Tortinita 树的 DFS 顺序为 $$$a_0, a_1, \ldots, a_n$$$,Arietta 树的 DFS 顺序为 $$$b_0, b_1, \ldots, b_n$$$。您观察到 $$$a_0 = b_0 = 0$$$,并且由于她们是双胞胎姐妹,您想知道她们是否可以拥有完全相同的树。因此,您想要 找出两个序列的不同公共树的数量$$$^{\text{*}}$$$。由于答案可能非常大,因此需要对 $$$998\,244\,353$$$ 进行模输出。

$$$^{\text{*}}$$$如果存在一个顶点标签,且其子标签集在两棵树中不相同,则两棵树被视为不同。换句话说,任何给定顶点的子级顺序并不重要。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le \boldsymbol{5000}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \cdots, b_n$$$ ($$$1 \le b_i \le n$$$)。

保证序列 $$$a$$$ 和 $$$b$$$ 都不包含重复项。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$2.5\cdot10^7$$$。

输出

对于每个测试用例,输出一个整数——不同公共树的数量以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

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

输出
复制

2
1
3
7

注意

在第一个测试用例中,两棵不同的树是下图中的树 A 和树 B。请注意,树 B 和树 C 是相同的。

在第二个测试用例中,唯一的公共树是树 B。