Số lượng playlist nhạc trong C++

Có N bài hát khác nhau, muốn nghe L bài trong chuyến đi. Playlist phải: (1) Mọi bài hát đều được chơi ít nhất 1 lần. (2) Một bài hát chỉ được chơi lại sau khi đã nghe K bài khác. Đếm số playlist hợp lệ modulo 10^9+7.

Ví dụ: N=2, L=3, K=0 → 6 playlist.

Giải thuật

1. DP: dp[i][j] = số playlist độ dài i dùng đúng j bài hát khác nhau.
2. Cơ sở: dp[0][0] = 1.
3. Chuyển trạng thái:
   • Thêm bài hát mới: dp[i][j] += dp[i-1][j-1] * (N - (j-1)).
   • Thêm bài hát cũ (chỉ nếu j > K): dp[i][j] += dp[i-1][j] * (j - K).
4. Kết quả dp[L][N].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
    int add(lli a, lli b){ return ((a % m) + (b % m)) % m; }
    int sub(lli a, lli b){ return ((a % m) - (b % m) + m) % m; }
    int mul(lli a, lli b){ return ((a % m) * (b % m)) % m; }
    int numMusicPlaylists(int N, int L, int K) {
        vector<vector<int>> dp(L + 1, vector<int>(N + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= L; i++)
            for(int j = 1; j <= N; j++) {
                dp[i][j] = mul(dp[i-1][j-1], (N - (j - 1)));
                if(j > K) dp[i][j] = add(dp[i][j], mul(dp[i-1][j], j - K));
            }
        return dp[L][N];
    }
};
int main(){
    Solution ob;
    cout << (ob.numMusicPlaylists(2, 3, 0));
}

Đầu vào

2,3,0

Đầu ra

6