[ARC143] B - Counting Grids

[Q] https://atcoder.jp/contests/arc143/tasks/arc143_b

考察
1. 全体の階乗から、ダメケースを除こうと思う
2. ダメな例？

N = 4の場合
[4]5 6 7
 3
 2
 1

4のマスが問題条件を満たさないのでダメケースに該当する。
行の最小値であり、列の最大値になる。

また、4以外のマスで条件を満たさないマスを産むことはできない。
2マス以上ダメケースは考えなくていい。

このバリエーションがどれだけあるかを考える。

1. 123を動かす。
3P3 = 6 通り

2. 567を動かす。
これは、5~16の12通りが入るので、
12P3 通り。

3. それ以外の9ます
[4]5 6 7
 3 x x x
 2 x x x
 1 x x x
好きな数字を入れていいので、9!通り

4. マス4の位置
5[4]6 7
  3
  2
  1
行にずらしてもいいし、

 3
[4]5 6 7
 2
 1
列にずらしてもいい。
これは4*4通り

5. ダメなマスは、4 ~ 13まで取りうるので、それぞれについて減算する。

以上から、
all = 16!
dis =  マス4: 3P3 * 12P3 * 9! * 16
     + マス5: 4P3 * 11P3 * 9! * 16
     + マス6: 5P3 * 10P3 * 9! * 16
     + ...
     + マス13: 12P3 * 3P3 * 9! * 16

all - dis が答え。

実装

int main() {
 cincout();

 ll N;
 cin >> N;

 mint ans = 1;
 // N=4 16!
 for (ll i = 2; i <= N * N; ++i) ans *= i;
 mint add = 1;
 // 3*3が自由枠
 for (ll i = 2; i <= (N - 1) * (N - 1); ++i) add *= i;
 // 4~13まで
 for (ll i = N; i <= N * (N - 1) + 1; ++i) {
   mint dis = 1;
   rep(j, N - 1) dis *= i - 1 - j; // 3,2,1
   rep(j, N - 1) dis *= N * N - i - j; // 16-4,16-5,16-6
   dis *= N * N;  // iの置き場所
   dis *= add;
   ans -= dis;
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/arc143/submissions/32776064