ABC127 E. Cell Distance

問題

N*Mのマス目のKマスに1つずつ駒を置くことを考える。
ここで、K個の駒が(x1,y1), ...., (xK,yK)と置かれるときの配置コストを
Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
とする。
駒のすべての配置の仕方のコストを考えたとき、その配置コストの総和を10^9+7で割ったあまりで求めよ。

制約

• 2 <= N*M <= 2*10^5
• 2 <= K <= N*M
• 入力はすべて整数

解法

問題は、
Σ_{すべてのあり得る駒の配置} Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
= Σ_{すべてのあり得る駒の配置} (すべての駒のペアについてそのマンハッタン距離を求めたときの合計値)
を求めよ、ということを言っている。

ある2つの駒が(xi,yi)と(xj,yj)に置かれる状況を考えると、この2つの駒がそこに置かれるような配置は、この2つ以外の駒がこの2か所以外に置かれる通りだけあり得るので、(M*N-2)_C_(K-2)通りだけ答えの中で出現している。
しかし、これを使って求めるのだとペアを決めるのにO(N*M * N*M)かかってしまうため、もっとまとめ上げて計算してあげる必要がある。

まず、マンハッタン距離の性質として、x軸とy軸は独立に求められるので、xだけを考える。(ただし、駒の配置は2次元のまま考える)

まとめあげとして、|xi-xj|を求めたいので2つの駒の距離に注目すると、この距離がdであるような場合を考える。
距離がdであるようなx軸の選び方は(M-d)通りあり、選んだ軸の左側と右側それぞれN通り置き方があり得るので、結局、(M-d)*N*N通りあることがわかる。(距離dは1～Mまで考えればよい)

したがって、求めたい値のx軸については以下のようになる。
Σ_{d=1}^{M} d * (M-d)*N*N * (M*N-2)_C_(K-2)
これをNとMをひっくり返してy軸についても同様に求めてあげれば答えが求まる。

計算量は、組み合わせの計算の部分が重くて実装方法次第だが、O(N*M)程度。

反省

• 問題を誤読＆制約を見間違っていた(N,Mと思ったがN*Mだった)
  • 制約はなんか同じような見間違いをしていた人が多かった模様
  • なんか問題読解にミスってることが最近多い気がするので、ちゃんと時間かけて読むようにする
• 組み合わせ問題は、言い換えが重要なので、どういう言い換えをしているかなど知見を貯める