第 6 回 ドワンゴからの挑戦状 予選-C Cookie Distribution 解説
解説 AC
組み合わせ苦手すぎる…
解説
求める値は、全ての配り方におけるうれしさの総和である。
ここで、うれしさを「子供が持っているクッキーの中から $1$ 枚を選ぶ方法の数」と言い換える。（これがめちゃくちゃ重要）
選ばれるクッキーを配った日ごとに分類して $x_1,x_2,\cdots x_K$ とすると、これらを子供に割り当てる方法の数は $\frac{N!}{\Pi_{i=1}^K x_i!}$ になる。また、残りのクッキーの配り方は、残り $N-x_i$ 人に $a_i - x_i$ 枚を配るので、$\binom{N-x_i}{a_i-x_i}$ となる。
これらを、ありうる全ての $x$ の組について足し合わせればよいが、これは DP で解けるので、 $O(N^2K)$ でこの問題が解けた。
感想
言い換え、大事！
