Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

AtCoder AGC025 B RGB Coloring (解説記事ではない)

問題

B - RGB Coloring

解法

赤と青を独立に塗るだけ.

note

{S = \{ (x’,y') | x',y'\in \mathbb Z, 0 \leq x',y' \leq N,  x'A+y'B=K\}}

とする.まず{ (x,y)\in S} を1つ固定し,A点をx回,B点をy回得てK点にする組み合わせを考える.

緑色に塗る個数をi個で固定すると,赤x-i個 青y-i個 緑i個 無(N-x-y+i)個の組み合わせとなるので,塗り方は

{\displaystyle \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}} 通り.

iを動かすことでA点をx回,B点をy回得てK点にする方法の総数が求められ,

{\displaystyle\sum_{i=0}^{\min(a,b)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}}通り.

よって答えは

{ans = \displaystyle \sum_{(x,y)\in S} \sum_{i=0}^{\min(a,b)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!}}

なのだが,解説の通り赤と青は独立に考えることができるので,

{ans = \displaystyle \sum_{(x,y)\in S} \frac{N!}{x!(N-x)!}\frac{N!}{y!(N-y)!}}.

ここから

{\displaystyle \sum_{i=0}^{\min(x,y)} \frac{N!}{(x-i)!(y-i)!i!(N-x-y+i)!} = \frac{N!}{x!(N-x)!}\frac{N!}{y!(N-y)!}}

という等式が得られる??