CF1906J Count BFS Graph

你正在研究一种称为广度优先搜索（BFS）的图遍历算法。假设你有一个包含 $N$ 个节点（编号为 $1$ 到 $N$）的输入图。该图由邻接矩阵 $M$ 表示，如果节点 $u$ 能遍历到节点 $v$，则 $M_{u, v} = 1$，否则为 $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$ 取模后的结果。

一个简单图没有自环（即 $M_{i, i} = 0$，$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 的说明 下图展示了所有满足要求的图。  样例输入输出 2 的说明 唯一满足要求的图是一个有两条边的图：一条连接节点 $1$ 和 $3$，另一条连接节点 $3$ 和 $2$。 由 ChatGPT 4.1 翻译