\(A_1 \geq A_2 \geq \ldots \geq A_N\) を満たすように適切に \(A\) と \(B\) をソートしているとします。 カンガルー \(i\) がカンガルー \(j\) のポケットの中に入っているようなすべての組 \((i,j)\) について頂点 \(j\) の子が頂点 \(i\) であるというような根つき木の集合を考えます。

\(dp[i][j][k]= (\) \(i\) 匹までのカンガルーについて操作を行ったとき、そのまま葉になってはいけない頂点の個数が \(j\) 個で葉である頂点が全体で \(k\) 個ある場合の数 \()\) とします。

答えるべき値は \(dp[N][0][1]+dp[N][0][2]+ \ldots +dp[N][0][N]\) です。

この \(dp\) を計算する時、新たに \(i+1\) 匹目のカンガルーを追加する際に遷移は以下の通りです。

• 他のカンガルーのポケットに入れないとしたとき
  • その時点で葉の頂点のうち \(A_{i+1}<B_x\) を満たす \(x (\leq i)\) の個数を \(l\) 個とすると \(dp[i+1][l][k+1]\) に \(dp[i][j][k]\) 加算する。\(l\) は \((i,j,k)\) の組について一意に定まります。なぜならば\(A_{i+1} \geq B_x\) を満たす \(x(\leq i)\) は必ず葉となっており、葉は \(k\) 個あるのでそのような \(x\) 以外は全て \(A_{i+1}<B_x\) を満たすからです。
• 葉になってはいけない頂点の子として定める
  • \(dp[i+1][j-1][k]\) に \(dp[i][j][k] \times j\) を加算する
• 葉である頂点の子として定める
  • \(dp[i+1][j][k]\) に \(dp[i][j][k] \times (l-j)\) を加算する

実装例(C++)