सी++ में संगीत प्लेलिस्ट की संख्या

मान लीजिए हमारे पास एक म्यूजिक प्लेयर है, जिसमें एन अलग-अलग गाने हैं और हम अपनी यात्रा के दौरान एल गाने सुनना चाहते हैं। इसलिए हमें एक प्लेलिस्ट बनानी होगी ताकि वह इन शर्तों को पूरा करे -

• हर गाना कम से कम एक बार बजाया जाता है

• एक गाना फिर से तभी चलाया जा सकता है जब K अन्य गाने बजाए गए हों।

हमें संभावित प्लेलिस्ट की संख्या का पता लगाना है। उत्तर बहुत बड़ा हो सकता है, इसलिए हम इसे मॉडुलो 10^9 + 7 लौटा देंगे।

इसलिए, यदि इनपुट एन =2, एल =3, के =0 जैसा है, तो आउटपुट 6 होगा, क्योंकि 6 संभावित प्लेलिस्ट हैं [1,1,2], [1,2,1], [2 ,1,1], [2,2,1], [2,1,2], [1,2,2]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम

• एक फ़ंक्शन उप () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) - (बी मॉड एम) + एम) मॉड एम

• फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम

• मुख्य विधि से, निम्न कार्य करें -

• dp(L + 1) x (N + 1)

  आकार का एक 2d सरणी बनाएं

• डीपी [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))

• वापसी डीपी [एल, एन]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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