順列 \((P_1,\dots,P_N)\) に対して、問題文で説明された数列を求めるアルゴリズムは以下のとおりです。

stack<int> st({0});
P[0] = 0;
vector<int> A(N + 1);
for (int i = 1; i <= N; ++i) {
  while (P[st.top()] > P[i]) st.pop();
  A[i] = st.top();
  st.push(i);
}

このアルゴリズムをもとに条件を言い換えると、各 \(i\) について、 while ループが st.back() が \(A_i\) になるまで回るような順列 \((P_1,\dots,P_N)\) の数を求めれば良いです。

この言い換えをもとに上記のアルゴリズムの挙動をシミュレーションすることで、\(P_i<P_j\) のような形の条件式が \(2N\) 個程度求まります。この大小関係を有向辺とみなしたDAGのトポロジカルソートのしかたの数が答えになりますが、このまま直接答えを求めるのは難しいです。

そこで、グラフを観察して条件を整理していきます。まず、各 \(i=1,\dots,N\) について while ループを抜け出したときの条件を確認すると、\(P_i > P_{A_i}\) です。この大小関係を辺とみなして \(0\) を根とする根付き木を考えます。各 \(i\) について、whileループが回ってる間に \(i\) と比較された頂点は、すべて互いに先祖と子孫の関係にあることが分かるので、推移律から、そのうち最も根に近いものとの間の大小関係のみが本質的です。以上をまとめると、根付き木としてみたときに、以下の \(2\) 条件が必要十分ということになります。

\(v\) の子が \(c_1,\dots,c_k\) であるとき、

• \(P_{c_i} > P_v\)
• \(c_1<\dots<c_k\) ならば \(P_{c_1} >\dots>P_{c_k}\)

これを満たす順列を数え上げるには、各部分木について、部分木内の頂点の相対的な順序のうち条件を満たすものを数え上げていけばよいです。計算量は全体で \(O(N)\) です。

C++による実装例