SRM531 Div1 300

問題

音楽プレイヤーに曲がN曲入っている。
プレイリストを作りたいが、P(>=N)曲で構成したい。
条件として、「全ての曲は必ず1回は流す」「すでに使った曲をもう一度流すためには間に少なくとも別なM曲をはさまなければならない」というルールを付ける。
このようなプレイリストの組み合わせは膨大なので、この組み合わせの数を1000000007でmodを取って答えよ。

考え方

DP。

重複組み合わせみたいなのをがんばろうとすると全部の状態みたいなのを考えたりして難しいことになる。
dp[それまで使った曲数][それまで使った曲の種類]。
１つ目のルール「全ての曲は必ず1回は流す」というのは、dp[P][N]のNで満たせる。
２つ目のルール「間にM曲はさむ」というのは、これまでj種類の曲を使って(dp[i-1][j])、さらにi曲目でj種類のうちのどれかを流すパターンだけど、j種類のうちM曲はなれないと使えないので、j>Mの時、dp[i-1][j]*(j-M)の組み合わせがある。
dpの更新式は、i-1曲目まででj-1種類使って、i曲目で新しい種類を使うパターンがあるので、新しい曲の数N-(j-1)を掛けて、dp[i-1][j-1]*(N-(j-1))の組み合わせがある。

上の2つの更新式でdp[i][j]をmodとりながら更新すれば、dp[P][N]が答えになる。
(dp[0][0]=1にする)