| 
N 曲から P 曲のプレイリストを作る。何種類作れるか。ただし N 曲すべて１回は使うこと。かつ、同じ曲を使う場合は間に M 曲以上おかないといけない。
N==P なら N! 通りである。ふむ。
最近の M 回はどれも違う曲だから、その次の曲は N-M 通りだな。ふむ。
じゃあ N! * (N-M)**(P-N) だと思って書いてみたけど、これだと最初の N 回で N 曲使うパターンしか見てないな。だめだ。
DP ぽいけど漸化式が思いつかん。
で、ちょっと考えて hard に行って戻ってきてやっぱりできず。
editorial などによると、dp[プレイリストの曲数][使った曲の種類数] == 可能なプレイリストの数 というきれいな式になるらしい。
dp[i][j] = dp[i-1][j-1] * (N-(j-1)) // 使ってない曲は N-(j-1) 種類 + dp[i-1][j] * max(j-M, 0) // 既に使った j 種類のうち、最近の M 曲は使えない。 // さらにその M 曲は全部異なるので j-M 曲使える
class NoRepeatPlaylist { public: int numPlaylists(int N, int M, int P) { ll mod = 1000000007LL; VVI dp(P+1, VI(N+1)); dp[0][0]=1; for(int i=1;i<=P;i++) for(int j=1;j<=N;j++) { dp[i][j] = (dp[i-1][j-1] * (N-(j-1)) + dp[i-1][j] * max(0, j-M)) % mod; } return dp[P][N]; } };
