मान लीजिए हमारे पास एक म्यूजिक प्लेयर है जिसमें N अलग-अलग गाने हैं और हम अपनी यात्रा के दौरान L गाने सुनना चाहते हैं। हमें एक प्लेलिस्ट बनानी है जो इन शर्तों को पूरा करती है:
हर गाना कम से कम एक बार बजाया जाए
एक गाना केवल तभी दोबारा बजाया जा सकता है जब K अन्य गाने बज चुके हों
हमें संभावित प्लेलिस्ट की संख्या ढूंढनी है। उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड्यूलो 10^9 + 7 में वापस करें।
उदाहरण के लिए, यदि N = 2, L = 3, K = 0, तो आउटपुट 6 होगा।
हल करने का दृष्टिकोण
हम डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
dp[i][j] = i लंबाई की प्लेलिस्ट जिसमें ठीक j अद्वितीय गाने हों
dp[0][0] = 1
संक्रमण: नया गाना जोड़ें: dp[i-1][j-1] * (N - (j-1))
पुराना गाना जोड़ें (यदि j > K): 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];
}
};
int main(){
Solution ob;
cout << (ob.numMusicPlaylists(2, 3, 0));
return 0;
}
इनपुट
2,3,0
आउटपुट
6
