定義など

ヤング図形

マスを上端と左端を揃えて並べた図形であって、各行にあるマスの数が単調非増加であるようなものをヤング図形という

こういうやつ

(図の出典: wikimedia)

マスの数をヤング図形の大きさという

標準タブロー

大きさ \(n\) のヤング図形の各マスに \(1\) から \(n\) の数を、「各行を左から右に見ると単調増加」かつ「各列を下から上に見ると単調増加」となるように \(1\) つずつ書き込んだものを標準タブローという

こういうやつ

(図の出典: wikimedia)

フック長の公式

与えられた大きさ \(n\) のヤング図形から標準タブローを作る方法が何通りあるかを (四則演算を \(O(1)\) として) \(O(N)\) で求めるフック長の公式というものが存在する。

en wikipedia: Hook length formula

ロビンソン・シェンステッド対応

「長さ \(n\) の順列からなる集合」と「大きさ \(n\) の同じ形の標準タブローの組からなる集合」の間に全単射が存在する。

具体的な構成は以下に譲る：
ヤング図形と競技プログラミング（公式解説からリンクされている箱星さんの記事）

以下では、ロビンソン・シェンステッド対応で順列 \(P\) と対応する標準タブローの組を \((S,T)\) と書いたとき、上記の記事の図の左側にあるものを \(S\)、右側にあるものを \(T\) とする。

LIS/LDSと標準タブローの形

ロビンソン・シェンステッド対応で順列 \(P\) と対応する標準タブローの組が \((S,T)\) であるとき、\(S,T\) の横の長さが \(P\) のLISの長さ、\(S,T\) の縦の長さが \(P\) のLDSの長さに一致する。

元の問題について

大きさ \(n\) の標準タブローの組 \((S,T)\) であって、ロビンソン・シェンステッド対応で対応する順列 \(P\) が条件を満たすものの性質を考える。

• \(S,T\) は、縦 \(B\) 横 \(A\) の長方形の右下が1マス欠けたものである。
• \(T\) は任意の標準タブローである
• \(S\) は標準タブローのうち「任意の \(i\) で \(S_{i,A-1}<S_{i-1,A}\)」を満たすものである。

\(T\) として取れるものの個数はフック長の公式から、\(S\) として取れるものの個数はDPにより求まるので、この積が答えである。