[1] 条件を整理する

どのような行列が条件を満たすかをいろいろ手で試し (またはプログラムを書いて列挙したものを観察し) 、どのような条件であるかを整理しましょう。

値が未決定のマスに \(0\) または \(1\) を書き込んでいくことを考えると、以下の条件が分かります。

• \(0\) の左に \(1\) があった場合、その下も \(0\) でないといけない
  
  • 下に \(1\) があったと仮定すると、それを含む \(4\) マスが不等式を満たさないため
    
• \(0\) の右に \(1\) があった場合、その上も \(0\) でないといけない
  
• \(0\) の上に \(1\) があった場合、その右も \(0\) でないといけない
  
• \(0\) の下に \(1\) があった場合、その左も \(0\) でないといけない
  

逆に、これらの条件を満たしている行列は数えるべき行列です。

[2] 条件に関わらない部分を削除する

\(0\) の左右に \(1\) があった場合、その列は全て \(0\) になります。

この \(0\) のみからなる列に注目しましょう。この列に関わる \(4\) マスを選択した場合 ( \(b\) または \(d\) にこの列を選んだ場合) 、不等式は必ず成立します。

したがって、行列が条件を満たすかどうかは、この列を取り除いたときの行列により決定されます。そこで、あらかじめ \(0\) のみからなる列を削除しておくことにしましょう。

\(m = 1, 2, \dots, M\) について、以下を求めれば良いです。(その後、どの列が削除されたかの二項係数 \(\binom Mm\) を掛けて足し合わせる)

• 大きさ \(N \times m\) の \(\lbrace 0, 1 \rbrace\) からなる行列であって、以下の条件を満たすものの個数
  • 各列に \(1\) が存在する
  • \(A_{a,b} \times A_{c,d} ≤ A_{a,d} \times A_{b,c}\ (a < c,\ b < d)\)

[1] の条件は以下のように変更されます。

• \(0\) の左に \(1\) があった場合、その右下も \(0\) でないといけない
  
• \(0\) の右に \(1\) があった場合、その左上も \(0\) でないといけない
  
• \(0\) の上に \(1\) があった場合、その右も \(0\) でないといけない
  
• \(0\) の下に \(1\) があった場合、その左も \(0\) でないといけない
  

---

\(0\) のみからなる行も同様に条件に関わらない部分なので、これもあらかじめ削除しておくことにしましょう。

\(n = 1, 2, \dots, N\) と \(m = 1, 2, \dots, M\) の全ての組み合わせについて、以下を求めれば良いです。(その後、どの行・列が削除されたかの二項係数 \(\binom Nn\binom Mm\) を掛けて足し合わせる)

• 大きさ \(n \times m\) の \(\lbrace 0, 1 \rbrace\) からなる行列であって、以下の条件を満たすものの個数
  • 各行に \(1\) が存在する
  • 各列に \(1\) が存在する
  • \(A_{a,b} \times A_{c,d} ≤ A_{a,d} \times A_{b,c}\ (a < c,\ b < d)\)

[1] の条件は以下のように変更されます。

• \(0\) の左に \(1\) があった場合、その右下も \(0\) でないといけない
  
• \(0\) の右に \(1\) があった場合、その左上も \(0\) でないといけない
  
• \(0\) の上に \(1\) があった場合、その右下も \(0\) でないといけない
  
• \(0\) の下に \(1\) があった場合、その左上も \(0\) でないといけない
  

この \(4\) つを整理すると、以下の \(1\) つの条件に集約されます。

• 左上と右下に \(1\) があった場合、その間の長方形領域も \(1\) でないといけない (★)
  

[3] 条件を満たす行列の形を観察する

条件を満たす行列の形を観察すると、左下から右上へ \(2\) 本の線を引き、その間の領域が \(1\) 、それ以外の領域が \(0\) という風になっていることがわかります。

ここで、各行 / 各列に \(1\) が存在しなければならないことに注意しましょう。すなわち、\(2\) 本の線が合流したらすぐに離れなければなりません。

この形が十分条件であることは (★) を満たしていることから明らかで、必要条件であることは (★) の条件から示すことができます。

[4] 動的計画法で行列の数を数える

\(n, m\) を \(1\) つ固定したとき、この形の行列の数は以下の DP により求めることができます。

\(\text{dp}[i][l][r] := {}\)( \(i\) 行目の \(1\) のある列が \(l\) 列目から \(r\) 列目であるときの、上 \(i\) 行への条件を満たす数字の書き込み方の数)

これを愚直に計算すると \(O(nm^4)\) 時間になりますが、累積和により \(O(nm^2)\) 時間で計算することができます。

あとは、これを全ての \(n, m\) について計算し、適切な係数をかけて足し合わせれば良いです。このままでは \(O(N^2M^3)\) 時間になってしまいますが、

• DP の遷移は掛け算と足し算のみで計算されている
• ある \(n, m\) のときの DP の計算は、\(n = N, m = M\) のときの DP の計算の一部になっている
• DP の計算結果が答えに与える寄与の係数 \(\binom Nn\binom Mm\) は \(n\) に関わる部分と \(m\) に関わる部分に分解できる

ことに注目すると、全ての \(n, m\) についての計算を重ね合わせて、同時に計算することが可能です。これにより、この問題を \(O(NM^2)\) 時間で解くことができました。

実装例 (C++)