No.023 C

$i$ 行目の飴の数 $n_r(i)$ と $j$ 列目の飴の数 $n_c(j)$ をあらかじめ計算する.

飴のあるマスに移動したときは $n_r(i) + n_c(j) = K+1$ となれば獲得する飴の数を $K$ にすることができ, 飴のないマスに移動したときは $n_r(i) + n_c(j) = K$ となれば獲得する飴の数を $K$ にすることができる.

まず, 飴のあるマスに移動したときに $n_r(i) + n_c(j) = K+1$ となる組み合わせを数える. これは $n_r, n_c$ を計算済なので $O(N)$ で計算できる.

そして, 飴のないマスに移動したときに $n_r(i) + n_c(j) = K$ となる組み合わせを数える. まずはすべてのマスで $n_r(i) + n_c(j) = K$ となる組み合わせを数え, そこから飴のあるマスで $n_r(i) + n_c(j) = K$ となる組み合わせを引く.

すべてのマスの組み合わせは $n_c(j) = k$ となる列数をあらかじめ数えておき, 行ごとに $n_c(j) = K - n_r(i)$ となる列数を計算して合計すればいい.