ABC 127 E - Cell Distance

• 問題
• AC

ひと目でわからなかったので、まずは問題を１次元に変えたものを解くことに集中した。これが解けなければ２次元の場合はまず解けない。（こういう考察スタイルに慣れてきた。）

１次元区間$\{1, ..., N\}$上に$K$個の駒を置く問題を考える。2点$s, t \in \{1, ..., N\}$が与えられたとき、$|s-t|$が何回足されるかを考えると、$s, t$以外の駒の置き方は$\binom{N-2}{K-2}$通りなので$\binom{N-2}{K-2}$回足されることがわかる。また、$|s-t|=1$であるような$s, t$の組み合わせは$N-1$通り、$|s-t|=2$であるような組み合わせは$N-2$通り、……と数えられるので、すべての$s,t$の組み合わせについて足し合わせると

$\binom{N-2}{K-2}(1 \cdot (N-1) + 2 \cdot (N-2) + ... + (N-1) \cdot 1)$

となり、これが１次元の場合の答えである。

２次元の場合もあまり変わらない。やはり$s, t \in \{1, ..., N \}$が与えられたとする。$s, t$行目にあるような2つの駒の置き方は$M^2$通りあり、それ以外の$K-2$個の駒の置き方が$\binom{NM-2}{K-2}$なので、$|s-t|$は$M^2 \binom{NM-2}{K-2}$回足されることになる。つまり、行に関する和（=問題の$|x_i-x_j|$の和）は

$M^2\binom{NM-2}{K-2}(1 \cdot (N-1) + 2 \cdot (N-2) + ... + (N-1) \cdot 1)$

であり、列に関する和も同様に

$N^2\binom{NM-2}{K-2}(1 \cdot (M-1) + 2 \cdot (M-2) + ... + (M-1) \cdot 1)$

と表される。これらを足せば答えになる。

考察は順調に進んだのだが、制約を$N, M \le 2 \times 10^5$と勘違いしてしばらく困っていた。