beet's soil

競プロのことなど

AtCoder Regular Contest 112 E - Cigar Box

想定解と違うことをしていたので

最終的に 操作で左に動かしたのが $L$ 個、右に動かしたのが $R$ 個みたいなのを固定しないと無理そう

Leftmost Ballっぽいな〜という気持ちになる

$ m $ 個の操作を $L + R$ 色で塗る これは $ \left( [x^m](\exp(x) - 1)^{L+R} \right) \cdot m! / (L+R)!$ 通り

各色について、最後の操作は左右が決まって、それ以外はどっちでもいい、$2^{m-(L+R)}$ みたいな係数がかかる

各色を左右に割り振るのは $\binom{L+R}{L}$ 通りある

$k = \max(n,m) $ として全体で $O(k^2 \log k)$ とか

提出 

atcoder.jp