CCF GESP 2026年9月认证 C++ 7级

给定一张有 $n$ 个结点 $m$ 条边的有向图 $G$，$G$ 中的结点依次以 $1,2,…,n$ 编号。第 $i$ 条边（$1≤i≤m$）从结点 $u_{i}$ 指向结点 $v_{i}$。

$G$ 中任一入度为 $0$ 的结点可以作为合法起点，任一出度为 $0$ 的结点可以作为合法终点。

如果 $G$ 中所有可能的从合法起点到合法终点的路径都会经过结点 $u$，则称 $u$ 是必经点。注意必经点可以为合法起点或合法终点。

请你求出 $G$ 中所有必经点的编号。

例如，在下图中合法起点有点 $1$ 与点 $2$，合法终点有点 $7$ 与点 $8$。

所有合法起点到合法终点的路径为：

• $1→3→4→5→7$
• $1→3→4→5→6→7$
• $1→3→4→5→6→8$
• $2→3→4→5→7$
• $2→3→4→5→6→7$
• $2→3→4→5→6→8$
• $2→4→5→7$
• $2→4→5→6→7$
• $2→4→5→6→8$

因此必经点有两个，编号分别为 $4,5$。

对于字符串 $S$ 与 $T$，如果从 $S$ 中删除任意多个字符可以得到 $T$，那么 $T$ 是 $S$ 的子序列。换言之，$T$ 是选取 $S$ 中的若干字符按下标顺序连接而成的。两个子序列不同当且仅当所选取的下标不同。

例如 sun 是 sequence 的子序列，因为从 sequence 中删除 eq、e 和 ce 可以得到 sun；sequence 有 $2^{8}$ 个不同的子序列，其中有空字符串，也有三个不同的子序列 e，因为 sequence 的第 $2,5,8$ 个字符都为 e，分别保留这三个字符得到的子序列是不同的。

对于字符串 $S$，如果 $S$ 满足以下条件那么 $S$ 是合法括号序列：

• $S$ 是空字符串，或者
• $S$ 可由 (、合法括号序列、) 三者连接得到，或者
• $S$ 可由两个合法括号序列连接得到。

例如 ()、()()、(()) 和 (()()) 都是合法括号序列。但是 (()、)( 不是合法括号序列。

给定一个长度为 $n$ 的仅包含 ( 与 ) 的字符串 $S$。请你求出 $S$ 所有 $2^{n}$ 个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对 $10^{9}$ 取模的结果。

例如，$S$ 为 ))(()( 时共有 $3$ 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 ()。