区間DPによって解くことを考えます。 何を数えるかで \(2\) 通りの方法があります。

解法 \(1\) : 根付き木を数える解法

まず、\(dp[l][r]\) \((1\leq l\leq r\leq N)\) を、

• \(A_l,A_{l+1},\ldots, A_r\) を頂点とし、頂点 \(A_l\) を根とするような \((r-l+1)\) 頂点の根付き木である。
• 根から始めて問題中と同じ方法で深さ優先探索を行った時に行きがけ順が \(A_l,A_{l+1},\ldots, A_r\) となる。

の \(2\) 条件をみたすものの個数として定めます。 求めたいものは \(dp[1][N]\) です。

さらに、\(dp'[l][r]\) \((1\leq l\leq r\bm{<} N)\) を、上の \(2\) 条件に加えて

• \(A_l\) の子として \(A_{r+1}\) を加えた木を考えた時、同様に深さ優先探索を行った時の行きがけ順が \(A_l,A_{l+1},\ldots, A_r, A_{r+1}\) となる。

をみたすものの個数として定めます。

このとき、\(dp[l][r]\) は、\(l=r\) のとき \(dp[l][r]=1\) であり、そうでないとき、\(2\) 条件をみたす木を頂点 \(A_l\) の子のうち番号が最大のもの（行きがけ順の条件から、\(A_l\) の子 \(A_{c_1},A_{c_2}\) について\(A_{c_1}<A_{c_2}\) と \(c_1<c_2\) が同値であることに注意）について分類することで、

\[ dp[l][r]=\displaystyle\sum_{k=l}^{r-1} (dp'[l][k]\times dp[k+1][r]) \]

と書くことができます。

また、\(dp'[l][r]\) も同様に考える事によって、\(l=r\) のとき \(dp[l][r]=1\) 、そうでないとき、

\[ dp'[l][r]=\displaystyle\sum_{\substack{l\leq k\leq r-1 \\ A_{k+1}<A_{r+1}}} (dp'[l][k]\times dp[k+1][r]) \]

として求めることができます。

配列の大きさは \(O(N^2)\) であり、それぞれの計算にかかる計算量も \(O(N)\) であることから、全体で\(O(N^3)\) です。定数倍が軽いことも踏まえると、これは十分間に合います。よって、この問題を解くことができました。

解法 \(2\) : 仮想頂点を根とした根付き木の数を数える解法

同様に区間 DP で解くことを考えます。 今度は \(dp[l][r]\) \((2\leq l\leq r\leq N+1)\) を、

• \(0, A_l,A_{l+1},\ldots, A_{r-1}\) を頂点とし、頂点 \(0\) を根とするような \((r-l+1)\) 頂点の根付き木である。
• 根から始めて問題中と同じ方法で深さ優先探索を行った時に行きがけ順が \(0, A_l,A_{l+1},\ldots, A_{r-1}\) となる。

の \(2\) 条件をみたすものの個数として定めます。ここで、求めたい値は \(dp[2][N+1]\) であることに注意します。なぜなら頂点 \(0\) を頂点 \(1\) に置き換えることで、数えたいものにちょうど一致するからです。

まず、\(l=r\) のときは\(dp[l][r]=1\) です。 そうでないとき、まず、条件をみたす木について頂点 \(A_l\) は頂点 \(0\) の子です。それ以外に頂点 \(0\) が子を持たない場合は残りの頂点は全て頂点 \(A_l\) の子孫であり、\(dp[l+1][r]\) 通りあります。それ以外に頂点 \(0\) が子を持ち、次に大きい頂点が頂点 \(A_k\) のとき、\(A_{l+1},\ldots, A_{k-1}\) は頂点 \(A_l\) の子孫でありこれが \(dp[l+1][k]\) 通り、一方、頂点 \(A_l\) とその子孫を取り除いた木としてあり得るものは \(dp[k][r]\) 通りあり、この積となります。ただし、\(A_l<A_k\) である必要がある事に注意します。

よって、\(dp[l][r]\) の計算式は、

\[ dp[l][r]=dp[l+1][r]+\displaystyle\sum_{\substack{l+1\leq k<r \\ A_l<A_k}} (dp[l+1][k]\times dp[k][r]) \]

となります。

計算量はこちらも同様に \(O(N^3)\) となり、十分高速です。

c++による実装例（解法 \(1\) ） :

#include <bits/stdc++.h>
using namespace std;

#define MOD 998244353

int main() {
	int n;
	int a[501];
	long long dp[501][501][2];

	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	a[n + 1] = n + 1;

	for (int r = 0; r < n; r++) {
		for (int i = 0; i < 2; i++)dp[r][r][i] = 1LL;
		for (int l = r - 1; l >= 0; l--) {
			for (int i = 0; i < 2; i++)dp[l][r][i] = 0LL;
			for (int k = l; k < r; k++) {
				dp[l][r][0] = (dp[l][r][0] + (dp[l][k][1] * dp[k + 1][r][0])) % MOD;
				if (a[k + 1] < a[r + 1])dp[l][r][1] = (dp[l][r][1] + (dp[l][k][1] * dp[k + 1][r][0])) % MOD;
			}
		}
	}

	cout << dp[0][n - 1][0] << endl;
	return 0;
}

c++による実装例（解法 \(2\) ） :

#include <bits/stdc++.h>
using namespace std;

#define MOD 998244353

int main() {
	int n;
	int a[500];
	long long dp[501][501];

	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];

	for (int l = n; l >= 1; l--) {
		dp[l][l] = 1;
		for (int r = l + 1; r <= n; r++) {
			dp[l][r] = dp[l + 1][r];
			for (int k = l + 1; k < r; k++) {
				if (a[l] < a[k])dp[l][r] = (dp[l][r] + (dp[l + 1][k] * dp[k][r])) % MOD;
			}
		}
	}

	cout << dp[1][n] << endl;
	return 0;
}