B - Counting Grids Editorial by yutaka1999


どんな書き込み方についても,\(2\) つの条件をともに満たさないようなマスは高々 \(1\) つしか存在しません.というのも,そのようなマスは次の条件を満たすからです.

  • 同じ列に書かれている数は,そのマスに書かれている数より小さい.
  • 同じ行に書かれている数は,そのマスに書かれている数より大きい.

この \(2\) つの条件を満たすマスが存在するような書き込み方の個数を数えます.そのマスの位置は \(N^2\) 通りあり,また,そのマスと同じ列・行に書かれている数の集合は \(\binom{N^2}{2N-1}\) 通りあります.それぞれごとに,数の書き込み方は \((N-1)!\times (N-1)!\times (N-1)^2!\) 通りなので,これらを掛け合わせることで答えが求まります.

posted:
last update: