ABC127 E - Cell Distance
問題原文
問題要旨
のグリッドがある。このグリッドに区別のつかない 個のコマを、各マスにつき最大1つ配置する。
また 個のコマの、ある配置の仕方についてのコストを、 と定める。
全ての配置の仕方についてのコストの総和を求めよ。ただし配置が異なるとは、片方の配置ではコマがあるが、もう一方にはないようなものをいう。
解法
いくつかのステップに分かれてます。
制約が完全に罠 ではないので気をつけましょう。いや罠すぎる。
と を分けて考える
こういうのは と について分けて考えるのがおすすめです。最後にそれぞれのコストの総和を足し合わせればよいです。
ここからは 、つまり横方向についてのみ考えていきます。とりあえずある行にコマを2個おいてみる
とりあえずおいてみます。
黄色マスがコマを配置すると決めたところです。この2つのマス間の距離は3ですが、これは何回数えられるでしょうか?
答えは、 マスからすでに2マス使っていて、加えて コマからすでに2つ使っているので、 通りになります。
でも実際には縦に 行分グリッドが続くので、 通りになります。マス間の距離が になるようなものは何通りあるか?
「ある2つのマスを決めた時に、そのコストが何回カウントされるか」はわかりましたが、まだ間に合いません。
二つのマス間の距離が同じであるならば、それらはまとめて計算できるので、今度は「マス間の距離が になるようなものは何通りあるか?」を考えていきます。
これは、ある1行に着目した場合には 個になります。( 個先にマスが存在するようなものは、 マス目までしかありません)
でもこれも3と同じように、縦に 行分グリッドが続くのでそれらを考慮してやる必要があります。
実際には、必ずしも同じ行に2コマを配置する必要がないので2行の選び方が 通りになって、結局マス間の距離が になるようなものは、 個あります。これらの計算を各 について行っても、 なので、十分間に合います。
これで、 についてのコストの総和を求めることができました。同じように についても計算して、足し合わせたものが答えになります。
実装
逆元コンビネーションは準備しておいてください。
H, W, K = map(int, input().split()) MOD = 10 ** 9 + 7 ans = 0 # Hについて for d in range(1, H): ans += d * (H - d) * pow(W, 2, MOD) * nCr(H * W - 2, K - 2) % MOD ans %= MOD # Wについて for d in range(1, W): ans += d * (W - d) * pow(H, 2, MOD) * nCr(H * W - 2, K - 2) % MOD ans %= MOD print(ans % MOD)
感想
HとWを分けて考える というのはとても大事なとっかかりですね。
あとは丁寧に考察を積み上げれば解ける、解いてて楽しい問題だと思います。
ただし制約、テメーはダメだ。