ABC127 E - Cell Distance (500)
縦横の距離の和はそれぞれ別々に計算できる
(i, j)からの距離の和を考える
左方向の距離の和は$ \frac{i(i+1)}{2}\times m
右方向の距離の和は$ \frac{(n - 1 - i)(n - i)}{2}\times m
上方向の距離の和は$ \frac{j(j+1)}{2}\times n
下方向の距離の和は$ \frac{(m - 1 - j)(m - j)}{2}\times n
それぞれの2点について同時に点が存在する組み合わせは$ _{nm-2}C_{k-2}通り
各(i, j)の距離の和に出現回数かけて、最後に二重にカウントしているので2で割ったのが答え
各点から$ O(1)で距離の和が出せる
組み合わせの事前計算が$ O(MN)
合わせて$ O(MN+MN) = O(MN)