C++ এ মিউজিক প্লেলিস্টের সংখ্যা

ধরুন আমাদের একটি মিউজিক প্লেয়ার আছে, যেটিতে N বিভিন্ন গান রয়েছে এবং আমরা আমাদের ভ্রমণের সময় L গান শুনতে চাই। তাই আমাদের একটি প্লেলিস্ট তৈরি করতে হবে যাতে এটি এই শর্তগুলি পূরণ করে -

• প্রতিটি গান অন্তত একবার বাজানো হয়

• একটি গান শুধুমাত্র তখনই আবার বাজানো যাবে যদি K অন্যান্য গান বাজানো থাকে।

আমাদের সম্ভাব্য প্লেলিস্টের সংখ্যা খুঁজে বের করতে হবে। উত্তরটি অনেক বড় হতে পারে, তাই আমরা এটি মডিউল 10^9 + 7 ফেরত দেব।

সুতরাং, যদি ইনপুটটি হয় N =2, L =3, K =0, তাহলে আউটপুট হবে 6, কারণ 6টি সম্ভাব্য প্লেলিস্ট [1,1,2], [1,2,1], [2] ,1,1], [2,2,1], [2,1,2], [1,2,2]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন সাব() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) - (b mod m) + m) mod m

• একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• (a mod m) * (b mod m)) mod m

  ফেরত দিন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• dp(L + 1) x (N + 1) আকারের একটি 2d ​​অ্যারে তৈরি করুন

• 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