BBC 004 E - simple finalization

• 問題

（引き分けを除いて）ちょうど$k$回戦後に$M$人が残る場合の数を考える。最後に残るプレイヤーの選び方が$\binom{N}{M}$通りで、残りの$N-M$人に$k$回のうちのどこで負けるかを割り振る必要がある。これは写像十二相の「ボールも箱も区別できる・各箱に少なくとも1つのボールが入る」場合にあたり、第二種スターリング数で書くなら$k! \cdot S(N-M, k)$。あとは$k$回の各じゃんけんで勝ちになった手がそれぞれ$3$通りありえるので、全体としては$\binom{N}{M}\cdot k! \cdot S(N-M, k) \cdot 3^k$通りと計算できる。これを$k=1, 2, ..., N-M$について足せばよい。

計算量はスターリング数の求め方次第で、Min_25さんの記事によると${O}(N\log N)$でできるらしい。