SRM531 Div1 Easy - NoRepeatPlaylist

問題

n曲からp曲選んで、以下の条件を全て満たすようなプレイリストを作りたい
① n曲全てを最低1個ずつ含む
② 同じ曲2つの間には異なる曲がm曲以上は挟まっている
何通りのプレイリストが作れるか

1 <= n <= 100
0 <= m <= n
n <= p <= 100

解法

dp[i][j]: i曲あり、n曲のうちj曲を使ったプレイリストの数
とすると答えはdp[p][n]であり、遷移は

・もう使った曲をまた使う場合
使う曲の候補は、制約②より直前に使ったm曲は使えないからj-m曲
dp[i+1][j] += dp[i][j] * (j-m)

・まだ使っていない曲を使う場合
n-j曲残っているから
dp[i+1][j+1] += dp[i][j] * (n-j)

class NoRepeatPlaylist {
public:
	int numPlaylists(int n, int m, int p) {
		ll dp[114][514] = {};
		dp[0][0] = 1;
		rep(i,p) rep(j,n+1) {
			(dp[i+1][j] += dp[i][j] * max(0, j-m)) %= mod;
			(dp[i+1][j+1] += dp[i][j] * (n-j)) %= mod;
		}
		return (int)dp[p][n];
	}
};

これが300点？