この問題は、ロビンソン・シェンステッド対応の練習問題です。

ロビンソン・シェンステッド対応自体については以下の記事が詳しいので参考にしてください。

ヤング図形と競技プログラミング(箱星さん)

今回の問題では、最長増加部分列（以下 LIS と表記）、最長減少部分列（以下 LDS と表記）の長さが指定されていること、\(P\) の長さが \(AB-1\) なことから、\(P\) の標準タブローの形が一意に定まります。

具体的には、縦 \(B\)、横\(A\) の長方形から右下の \(1\) マスを切り取ったものとなっています。\(i\) 行 \(j\) 列のマスをマス \((i,j)\) と呼ぶことにし、マス \((i,j)\) に書かれた数を \(t_{i,j}\) とします。今存在するマスは \((1,1),\ldots,(1,A),(2,1),\ldots,(2,A),\ldots,(B,1),\ldots,(B,A-1)\) です。また、任意の \(i,j\) について \(t_{i,j}<t_{i+1,j}, t_{i,j}<t_{i,j+1}\) が成立しています。

\(3\) 番目の制約について考えます。LIS と LDS が不変であることから、\(P\) の末尾に \(n+0.5\) を追加した結果、タブローの形は縦 \(B\)、横\(A\) の長方形に変化していることが分かります。最終的なタブローのマス \((i,j)\) に書かれた数を \(t'_{i,j}\) とすると、

• \(t'_{1,A}=n+0.5\)
• \(t'_{i+1,A}=t_{i,A}\ (1\leq i \leq B-1)\)

となります。これを満たすためには、元の \(t\) について

• \(t_{i,A}> t_{i+1,A-1}\ (1\leq i \leq B-1)\)

という条件が必要です。以上を整理すると、以下の条件を満たす \(t\) の個数を求められれば良いです。

• \(t\) には \(1\) 以上 \(AB-1\) 以下の整数が \(1\) 個ずつ含まれる
• \(t_{i,j}<t_{i+1,j}\)
• \(t_{i,j}<t_{i,j+1}\)
• \(t_{i+1,A-1}< t_{i,A}\)

\(4\) 個目の条件がなければフック長の公式を用いて簡単に答えが求まりますが、\(4\) 個目の条件が厄介です。

今回は制約が小さいことから、\(1,2,\ldots,AB-1\) の順に \(t\) の値を決めていくことにして dp をします。

状態数の評価をします。\(4\) 番目の条件がない場合でも、状態数はおよそ左下から右上へ右上移動を繰り返していく方法と対応していて、\(\binom{A+B}{A}\) 程度です。この値を制約の範囲内で試すと、状態数は最大ケースでも \(500000\) 以下ですので適切な実装のもと十分高速に動作します。