AtCoder AGC025 B RGB Coloring (解説記事ではない)
問題
解法
赤と青を独立に塗るだけ.
note
とする.まず を1つ固定し,A点をx回,B点をy回得てK点にする組み合わせを考える.
緑色に塗る個数をi個で固定すると,赤x-i個 青y-i個 緑i個 無(N-x-y+i)個の組み合わせとなるので,塗り方は
通り.
iを動かすことでA点をx回,B点をy回得てK点にする方法の総数が求められ,
通り.
よって答えは
なのだが,解説の通り赤と青は独立に考えることができるので,
.
ここから
という等式が得られる??