CF1906J.Count BFS Graph

You are currently researching a graph traversal algorithm called the Breadth First Search (BFS). Suppose you have an input graph of $N$ nodes (numbered from $1$ to $N$). The graph is represented by an adjacency matrix $M$, for which node $u$ can traverse to node $v$ if $M_{u, v}$ is $1$, otherwise it is $0$. Your algorithm will output the order the nodes are visited in the BFS. The pseudocode of the algorithm is presented as follows.

BFS(M[1..N][1..N]):
let A be an empty array
let Q be an empty queue

append 1 to A
push 1 to Q

while Q is not empty:
pop the front element of Q into u
for v = 1 to N:
if M[u][v] == 1 and v is not in A:
append v to A
push v to Q

return A

During your research, you are interested in the following problem. Given an array $A$ such that $A$ is a permutation of $1$ to $N$ and $A_1 = 1$. How many simple undirected graph with $N$ nodes and adjacency matrix $M$ such that $\text{BFS}(M) = A$? Since the answer can be very large, calculate the answer modulo $998\,244\,353$.

A simple graph has no self-loop ($M_{i, i} = 0$ for $1 \leq i \leq N$) and there is at most one edge that connects a pair of nodes. In an undirected graph, if node $u$ is adjacent to node $v$, then node $v$ is also adjacent to node $u$; formally, $M_{u, v} = M_{v, u}$ for $1 \leq u \lt v \leq N$.

Two graphs are considered different if there is an edge that exists in one graph but not the other. In other words, two graphs are considered different if their adjacency matrices are different.

你目前正在研究一种名为广度优先搜索（BFS）的图遍历算法。假设你有一个包含 $N$ 个节点（编号为 $1$ 至 $N$）的输入图。该图由邻接矩阵 $M$ 表示：若 $M_{u, v} = 1$，则节点 $u$ 可以到达节点 $v$；否则 $M_{u, v} = 0$。你的算法将输出 BFS 遍历节点的顺序。该算法的伪代码如下所示：

BFS(M[1..N][1..N]):
let A be an empty array
let Q be an empty queue

append 1 to A
push 1 to Q

while Q is not empty:
pop the front element of Q into u
for v = 1 to N:
if M[u][v] == 1 and v is not in A:
append v to A
push v to Q

return A

在研究过程中，你对以下问题产生了兴趣：给定一个数组 $A$，其中 $A$ 是 $1$ 到 $N$ 的一个排列，且满足 $A_1 = 1$。问：有多少个 $N$ 个节点的简单无向图，其邻接矩阵为 $M$，使得 $\text{BFS}(M) = A$？由于答案可能非常大，请对 $998\,244\,353$ 取模。

简单图指不含自环（即对所有 $1 \leq i \leq N$，均有 $M_{i, i} = 0$）且任意两个节点之间至多存在一条边的图。无向图中，若节点 $u$ 与节点 $v$ 相邻，则节点 $v$ 也与节点 $u$ 相邻；形式上，对所有 $1 \leq u < v \leq N$，均有 $M_{u, v} = M_{v, u}$。

若两个图中存在某条边仅属于其中一个图，则认为这两个图不同。换言之，两个图不同当且仅当它们的邻接矩阵不同。

The first line consists of an integer $N$ ($2 \leq N \leq 5000$).

The second line consists of $N$ integers $A_i$. The array $A$ is a permutation of $1$ to $N$ and $A_1 = 1$.

第一行包含一个整数 $N$（$2 \leq N \leq 5000$）。

第二行包含 $N$ 个整数 $A_i$。数组 $A$ 是 $1$ 到 $N$ 的一个排列，且满足 $A_1 = 1$。

Output an integer representing the number of simple undirected graphs with $N$ nodes and adjacency matrix $M$ such that $\text{BFS}(M) = A$. Since the answer can be very large, output the answer modulo $998\,244\,353$.

输出一个整数，表示满足条件的 $N$ 个节点的简单无向图的个数，其邻接矩阵为 $M$，且满足 $\text{BFS}(M) = A$。由于答案可能非常大，请对 $998\,244\,353$ 取模后输出。

Explanation for the sample input/output #1

The following illustration shows all graphs that satisfy the requirements.

Explanation for the sample input/output #2

The only graph that satisfies the requirements is a graph with two edges: one that connects nodes $1$ and $3$, and another one that connects nodes $3$ and $2$.

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

以下示意图展示了所有满足要求的图。

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

唯一满足要求的图包含两条边：一条连接节点 $1$ 和 $3$，另一条连接节点 $3$ 和 $2$。