問題概要
スマホにN曲の歌が入っている。
これらの曲を組み合わせてP曲のプレイリスト を作りたい。ただしプレイリストは以下の条件を満たす必要がある。
1) すべての曲は最低でも1回はプレイされなければならない
2) 同じ曲をプレイする場合は、最低でも間に別の曲をM曲プレイしなければならない
プレイリストの構成方法のパターン数を求めよ。
解法
よく分からななかったのでとりあえずDPしてみた。
const long long MOD = 1e9 + 7;
int N, M, P;
long long dp[124][124][124];
long long solve(int pos, int cnt, int ng) {
if (pos == P)
return cnt == N;
if (cnt > N)
return 0;
if (ng >= N)
return 0;
long long &ret = dp[pos][cnt][ng];
if (ret == -1) {
ret = 0;
ret += (cnt-ng) * solve(pos+1, cnt, min(ng+1, M));
ret += (N-cnt) * solve(pos+1, cnt+1, min(ng+1, M));
ret %= MOD;
}
return ret;
}
class NoRepeatPlaylist {
public:
int numPlaylists(int N, int M, int P) {
::N = N;
::M = M;
::P = P;
memset(dp, -1, sizeof(dp));
return solve(0, 0, 0);
}
};
より高速な解法
(1)の条件がなければ簡単に計算できることに注目して包除原理する。
N曲以下を使って(2)を満たすパターン数を数える。
これには、N-1曲しか使ってないパターンがあるのでそれを引く....
という感じに足して引いてを繰り返す。
const long long MOD = 1e9 + 7;
long long comb[128][128];
class NoRepeatPlaylist {
public:
int numPlaylists(int N, int M, int P) {
comb[0][0] = 1;
for (int i = 1; i < 128; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++)
comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
}
int sign = 1;
long long ret = 0;
for (int i = N; i > 0; i--) {
long long pat = 1;
for (int j = 0; j < P; j++)
pat = pat * max(i-j, i-M) % MOD;
ret += sign * pat * comb[N][i];
ret = (ret % MOD + MOD) % MOD;
sign = -sign;
}
return ret;
}
};
