Số lượng danh sách phát nhạc trong C ++

Giả sử chúng ta có một máy nghe nhạc chứa N bài hát khác nhau và chúng ta muốn nghe L bài hát trong chuyến đi của mình. Vì vậy, chúng tôi phải tạo một danh sách phát để nó đáp ứng các điều kiện này -

Mỗi bài hát được phát ít nhất một lần
Một bài hát chỉ có thể được phát lại nếu K bài hát khác đã được phát.

Chúng tôi phải tìm số lượng danh sách phát có thể. Câu trả lời có thể rất lớn, vì vậy chúng tôi sẽ trả về nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là N =2, L =3, K =0, thì đầu ra sẽ là 6, vì có thể có 6 danh sách phát [1,1,2], [1,2,1], [2 , 1,1], [2,2,1], [2,1,2], [1,2,2].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm sub (), điều này sẽ lấy a, b,
return ((a mod m) - (b mod m) + m) mod m
Xác định một hàm mul (), điều này sẽ nhận a, b,
return ((a mod m) * (b mod m)) mod m
Từ phương thức chính, thực hiện như sau -
Tạo một mảng 2d có kích thước dp (L + 1) x (N + 1)
dp [0, 0]:=1
để khởi tạo i:=1, khi i <=L, cập nhật (tăng i lên 1), thực hiện -
- để khởi tạo j:=1, khi j <=N, cập nhật (tăng j lên 1), thực hiện -
  - dp [i, j]:=mul (dp [i - 1, j - 1], (N - (j - 1)))
  - nếu j> K, thì -
    - dp [i, j]:=add (dp [i, j], mul (dp [i - 1, j], j - K))
trả về dp [L, N]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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];
   }
};
main(){
   Solution ob;
   cout << (ob.numMusicPlaylists(2, 3, 0));
}

Đầu vào

2,3,0

Số lượng danh sách phát nhạc trong C ++

Ví dụ

Đầu vào

Đầu ra