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を分けて考える というのはとても大事なとっかかりですね。
あとは丁寧に考察を積み上げれば解ける、解いてて楽しい問題だと思います。
ただし制約、テメーはダメだ。