C++の音楽プレイリストの数

N個の異なる曲を含む音楽プレーヤーがあり、旅行中にL個の曲を聴きたいとします。したがって、これらの条件を満たすようにプレイリストを作成する必要があります-

• すべての曲が少なくとも1回再生されます

• 曲を再度再生できるのは、他のK曲が再生された場合のみです。

可能なプレイリストの数を見つける必要があります。答えは非常に大きくなる可能性があるため、10 ^ 9+7を法として返します。

したがって、入力がN =2、L =3、K =0の場合、6つの可能なプレイリスト[1,1,2]、[1,2,1]、[2]があるため、出力は6になります。 、1,1]、[2,2,1]、[2,1,2]、[1,2,2]。

これを解決するには、次の手順に従います-

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数sub（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）-（b mod m）+ m）mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• メインの方法から、次のようにします-

• サイズdp（L + 1）x（N + 1）の2次元配列を1つ作成します

• dp [0、0]：=1

• 初期化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

出力

6