水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

CODE FESTIVAL 2018 Final:B - Theme Color

問題

atcoder.jp

解法

p = C(N, r_1) * C(N - r_1, r_2) * C(N - r_1 - r_2, r_3) * ... * C(r_M, r_M) / M^N

となる.これを愚直に計算すると,途中で数が大きくなりすぎてしまったり小さくなりすぎてしまったりするので,全体に log10 することで扱いやすくする.前計算を含めて O(N + M).

解答

atcoder.jp

f:id:babcs2035:20181231170304p:plain