[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;
}
この記事が気に入ったらサポートをしてみませんか?