AtCoder Beginner Contest 127：E - Cell Distance
問題
解法
まず，求める答えは x 方向の差の絶対値の合計と y 方向の差の絶対値の合計に分解できる．まず x 方向の差の合計について考える．ここで「差が k となるような 2 つの駒の置き方」を求める．これは x 方向の長さは M であるから x 方向上に置く置き方の通り数は k * (M - k) となり，この 2 つの駒は任意の y 座標を取りうるので N * N 通りをかけて，k * (M - k) * N^2 となる．y 方向に関しても N と M を入れ替えることによって求めることができる．今 2 つの駒について置き方を決めたので残りの K - 2 個の駒の置き方である C(N * M - 2, K - 2) をかける必要がある．コンビネーション計算が一番重くなり，全体で O(NM + N + M)．
解答
