C++의 음악 재생 목록 수

<시간/>

N개의 다른 노래가 포함된 음악 플레이어가 있고 여행 중에 L개의 노래를 듣고 싶다고 가정합니다. 따라서 이러한 조건을 충족하도록 재생 목록을 만들어야 합니다. -

모든 노래는 한 번 이상 재생됩니다.
K개의 다른 노래가 재생된 경우에만 노래를 다시 재생할 수 있습니다.

가능한 재생 목록의 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 N =2, L =3, K =0인 경우 가능한 재생 목록 [1,1,2], [1,2,1], [2]가 6개 있으므로 출력은 6이 됩니다. ,1,1], [2,2,1], [2,1,2], [1,2,2].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
함수 sub()를 정의하면, b,
return ((a mod m) - (b mod m) + m) mod m
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
기본 방법에서 다음을 수행하십시오 -
dp(L + 1) x (N + 1)
크기의 2차원 배열 하나를 만듭니다.
dp[0, 0] :=1
initialize i :=1의 경우 i <=L일 때 업데이트(i를 1만큼 증가), −
- j 초기화:=1의 경우 j <=N일 때 업데이트(j를 1만큼 증가), 수행 -
  - dp[i, j] :=mul(dp[i - 1, j - 1], (N - (j - 1)))
  - j> K이면 -
    - dp[i, j] :=add(dp[i, j], mul(dp[i - 1, j], j - K))
반환 dp[L, N]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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));
}

입력

2,3,0