TopCoder SRM 531 Div1

大敗北。

Result

Challenged / Opened / Unopened
398位 2097 -> 1960

Easy NoRepeatPlaylist

問題

N曲の曲からP曲を重複を許して、以下の条件を満たすよう選ぶ。
選び方は何通りあるか、mod 10^9 + 7で求めよ。


条件:
全ての曲が少なくとも一度以上選ばれる。
同じ曲は間に少なくともM曲のほかの曲を挟む。

制約条件

N,P,M≦100

試行錯誤

300点問題。
てかぱっと見なんか凄い苦手系統の問題に見えるんだけど。


少なくとも一度以上っていう条件どうするんだよ。
しかも間にM曲ほかの曲をはさむとか。


数十分考える。
包除原理だろうか。


全ての曲を一度以上選ばなくてもいいという条件があったら、
場合の数はN*(N-1)*(N-2)*……*(N-M)*(N-M)*(N-M)*…*(N-M)となるはずで。
うーん、N曲を一度以上選ぶ場合と、N-1曲を一度以上以上選ぶ場合と……
と部分集合になっているから包除原理でいける?


あ、いや、ボトムアップに、
1曲だけからなる場合と2曲だけからなる場合と……と計算していけば、
ちょうどk曲からなる場合の場合の数が求まる。


DPか。
書いた。おおすげえサンプルあった。
確認して送信。


もう時間ない。
残り15分。凄く萎えたので不貞寝。

System Test

300M≧Pの場合がコーナーケースになって落ちてるし。
年末年始にかけて猛練習したのに、ためたレートを一気に失った。
もうやだ。ひどい。


苦手っぽい300が一応自力で(コーナーケースの部分以外)解けたことはレベルアップしたとみていいんだろうか。