G - Pre-Order Editorial by en_translator
Consider solving it with segment DP (Dynamic Programming). There are two ways depending on what we count.
Solution \(1\): Counting rooted trees
First, let us define \(dp[l][r]\) \((1\leq l\leq r\leq N)\) to be the number of rooted trees such that:
- it has \((r-l+1)\) vertices, \(A_l,A_{l+1},\ldots, A_r\), and it is rooted at \(A_l\);
- the preordering starting from the root obtained in the same way as described in the problem statement is \(A_l,A_{l+1},\ldots, A_r\).
What we want to find is \(dp[1][N]\).
Moreover, we define additional DP table \((1\leq l\leq r\bm{<} N)\) to be the number of rooted trees that satisfy the two conditions above, plus:
- when \(A_{r+1}\) is added to the tree as a child of \(A_l\), the preordering obtained in the same way is \(A_l,A_{l+1},\ldots, A_r, A_{r+1}\).
Here, \(dp[l][r]\) is \(dp[l][r]=1\) if \(l=r\); otherwise, by classifying the trees satisfying the two conditions by the child of \(A_l\) with the maximum index (note that, due to the condition of the preordering, \(A_{c_1}<A_{c_2}\) and \(c_1<c_2\) are equivalent, where \(A_{c_1}\) and \(A_{c_2}\) are children of \(A_l\)), the value can be expressed as
\[ dp[l][r]=\displaystyle\sum_{k=l}^{r-1} (dp'[l][k]\times dp[k+1][r]). \]
We can consider \(dp'[l][r]\) in the same way: if \(l=r\), then \(dp[l][r]=1\), and otherwise
\[ 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]). \]
Since the size of the array is \(O(N^2)\) and each computation cost \(O(N)\) time, the whole algorithm costs \(O(N^3)\) time. Since the constant factor is fairly small, this easily fits in the time limit. Therefore, the problem has been solved.
Solution \(2\): Counting rooted trees with rooted at a virtual vertex
Just as before, consider solving it with segment DP. This time, we define \(dp[l][r]\) \((2\leq l\leq r\leq N+1)\) to be the number of rooted tree such that:
- it has \((r-l+1)\) vertices, \(0, A_l,A_{l+1},\ldots, A_{r-1}\), and it is rooted at \(0\);
- the preordering starting from the root obtained in the same way as described in the problem statement is \(0, A_l,A_{l+1},\ldots, A_{r-1}\).
Here, note that the value we want to find is \(dp[2][N+1]\), because the object we want to count can be obtained by replacing Vertex \(0\) with Vertex \(1\).
First, when \(l=r\), we have \(dp[l][r]=1\). Otherwise, first, in a tree that satisfies the condition, Vertex \(A_i\) is a child of Vertex \(0\). If that is the only child of Vertex \(0\), all other vertices are descendants of \(A_l\); there are \(dp[l+1][r]\) such trees. If Vertex \(0\) has other vertices, and if the next smallest vertex is Vertex \(A_k\), then Vertices are descendants of \(A_l\), in which there are \(dp[l+1][k]\) ways to do so; on the other hand, there are \(dp[k][r]\) possible trees as a result of removing Vertex \(A_l\) and its descendants. Note that it should hold that \(A_l<A_k\).
Therefore, the formula for \(dp[l][r]\) is
\[ 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]). \]
The time complexity for this solution is \(O(N^3)\), which is fast enough.
Sample code in C++ (Solution \(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;
}
Sample code in C++ (Solution \(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;
}
posted:
last update: