Number of Music Playlists

hard math dp combinatorics

Problem

You have n distinct songs and want a playlist of exactly goal songs in which every song appears at least once and no song repeats within k consecutive picks. Return the count mod 10^9+7.

Inputn=3, goal=3, k=1

Output6

dp[i][j] = playlists of length i using j distinct songs. Transition: pick a new (× (n-j+1)) or reuse (× max(j-k, 0)).

goal

def numMusicPlaylists(n, goal, k):
    MOD = 10**9 + 7
    dp = [[0]*(n + 1) for _ in range(goal + 1)]
    dp[0][0] = 1
    for i in range(1, goal + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j - 1] * (n - j + 1)
            if j > k:
                dp[i][j] += dp[i - 1][j] * (j - k)
            dp[i][j] %= MOD
    return dp[goal][n]

function numMusicPlaylists(n, goal, k) {
  const MOD = 1_000_000_007n;
  const dp = Array.from({ length: goal + 1 }, () => new Array(n + 1).fill(0n));
  dp[0][0] = 1n;
  for (let i = 1; i <= goal; i++) {
    for (let j = 1; j <= n; j++) {
      let v = dp[i - 1][j - 1] * BigInt(n - j + 1);
      if (j > k) v += dp[i - 1][j] * BigInt(j - k);
      dp[i][j] = v % MOD;
    }
  }
  return Number(dp[goal][n]);
}

class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final long MOD = 1_000_000_007L;
        long[][] dp = new long[goal + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1);
                if (j > k) dp[i][j] += dp[i - 1][j] * (j - k);
                dp[i][j] %= MOD;
            }
        }
        return (int)dp[goal][n];
    }
}

int numMusicPlaylists(int n, int goal, int k) {
    const long long MOD = 1000000007LL;
    vector<vector<long long>> dp(goal + 1, vector<long long>(n + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= goal; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j - 1] * (n - j + 1);
            if (j > k) dp[i][j] += dp[i - 1][j] * (j - k);
            dp[i][j] %= MOD;
        }
    }
    return (int)dp[goal][n];
}

Explanation

We are counting playlists of exactly goal songs drawn from n distinct songs, where every song appears at least once and no song repeats within k picks. The trick is a 2D table dp[i][j] = the number of valid playlists of length i that use exactly j distinct songs.

The base case is dp[0][0] = 1: one empty playlist using zero songs.

To build dp[i][j], the i-th slot is filled in one of two ways. Either we play a brand new song: there were j-1 distinct songs before, and n - (j-1) = n - j + 1 fresh ones to choose, giving dp[i-1][j-1] * (n - j + 1). Or we reuse a song we already played: among the j used songs, the last k are blocked, so j - k are legal — adding dp[i-1][j] * (j - k) (only when j > k). Everything is taken mod 10^9 + 7.

Example: n = 3, goal = 3, k = 1. Every one of the 3! = 6 orderings of the three songs is valid, so the answer is 6, matching dp[3][3].

The answer is dp[goal][n] — a full-length playlist that used all n songs. Filling the grid is O(n · goal).

Time: O(n · goal) Space: O(n · goal)