← 返回题目列表

Codeforces · 1906/J

J. 计数 BFS 图

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

您目前正在研究一种称为广度优先搜索 (BFS) 的图遍历算法。假设您有一个由 $$$N$$$ 节点组成的输入图(编号从 $$$1$$$ 到 $$$N$$$)。该图由邻接矩阵$$$M$$$表示,其中如果$$$M_{u, v}$$$为$$$1$$$,则节点$$$u$$$可以遍历到节点$$$v$$$,否则为$$$0$$$。您的算法将输出 BFS 中访问节点的顺序。该算法的伪代码如下所示。

在您的研究过程中,您对以下问题感兴趣。给定一个数组 $$$A$$$,使得 $$$A$$$ 是 $$$1$$$ 到 $$$N$$$ 的排列,并且 $$$A_1 = 1$$$。有多少个具有 $$$N$$$ 节点和邻接矩阵 $$$M$$$ 的简单无向图,使得 $$$\text{BFS}(M) = A$$$?由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模计算答案。

简单图没有自环($$$M_{i, i} = 0$$$ for $$$1 \leq i \leq N$$$)并且最多有一条边连接一对节点。在无向图中,如果节点 $$$u$$$ 与节点 $$$v$$$ 相邻,则节点 $$$v$$$ 也与节点 $$$u$$$ 相邻;形式上,$$$M_{u, v} = M_{v, u}$$$ 对于 $$$1 \leq u < v \leq N$$$。

如果一个图中存在边而另一个图中不存在,则两个图被视为不同。换句话说,如果两个图的邻接矩阵不同,则认为它们不同。

输入

第一行由整数 $$$N$$$ ($$$2 \leq N \leq 5000$$$) 组成。

第二行由 $$$N$$$ 整数 $$$A_i$$$ 组成。数组 $$$A$$$ 是 $$$1$$$ 到 $$$N$$$ 的排列,并且 $$$A_1 = 1$$$。

输出

输出一个整数,表示具有 $$$N$$$ 节点和邻接矩阵 $$$M$$$ 的简单无向图的数量,使得 $$$\text{BFS}(M) = A$$$。由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。

示例

输入 #1

3
1 2 3

输出 #1

3

输入 #2

3
1 3 2

输出 #2

1

输入 #3

5
1 3 2 4 5

输出 #3

17

输入#4

11
1 2 3 4 5 6 7 8 9 10 11

输出#4

379394847

注意

示例输入/输出#1 的说明

下图显示了满足要求的所有图表。

示例输入/输出 #2 的说明

满足要求的唯一图是具有两条边的图:一条连接节点 $$$1$$$ 和 $$$3$$$,另一条连接节点 $$$3$$$ 和 $$$2$$$。