Cell Distance - abc 127 e - tac

#組合せ

ずっと考えて AC できた

具体例で説明する

X, Y, K = 2, 3, 3
答えは 100

まず, x, y を分けて考える

x = 1 が何回足されて何回引かれるか考える

マス (1, 1) の x = 1 が何回出るか

マス (1, 1) は他の 5 マスと組みになれる
他の 5 マスから K-1 個選ぶ
${}_5 C_2 = 10$

そして, 10 組の中で, 2 つとペアになる
10 * 2 = 20

(1, 1), (1, 2), (2, 1)
(1, 1), (1, 2), (2, 2)
(1, 1), (1, 2), (3, 1)
(1, 1), (1, 2), (3, 2)

(1, 1), (2, 1), (2, 2)
(1, 1), (2, 1), (3, 1)
(1, 1), (2, 1), (3, 2)
(1, 1), (2, 2), (3, 1)
(1, 1), (2, 2), (3, 2)
(1, 1), (3, 1), (3, 2)

同じ x である (1, 2) も考えると,
20 * 2 = 40

これだけ x = 1 が出る
このうち, 何回足されて何回引かれて何回何もしないのか

まず, 何もしない分を引く

これは, x = 1 が K 個選ぶうちに何個出るかを探索して求める
i 個 x = 1 が出るとする

x = 1 は N 個ある
x = 1 でないのは NM - N 個ある
よって, ${}_N C_i * {}_{NM-N} C_{K-i}$

このうち, x = 1 どうしがペアになるのは ${}_i C_2$ 組みあり, 2 重になっているので *2 を引く

あとは, 足すか引くか

相手が自分より大きいと引くことになり, 自分より小さいと足すことになる

これは, 自分より大きいもの, 小さいものの割合を考えればいい