সমস্যা বিবরণ
Nটি আলাদা গান এবং L দৈর্ঘ্যের প্লেলিস্ট দেওয়া থাকলে, শর্তাবলী: ১) প্রতিটি গান কমপক্ষে একবার বাজবে, ২) একই গান আবার বাজাতে হলে মাঝপথে Kটি অন্য গান বাজতে হবে। সম্ভাব্য প্লেলিস্টের সংখ্যা বের করতে হবে (মডুলো 10^9+7)।
উদাহরণ
N=2, L=3, K=0 → আউটপুট = 6 (প্লেলিস্ট: [1,1,2], [1,2,1], [2,1,1], [2,2,1], [2,1,2], [1,2,2])
সমাধান পদ্ধতি
- DP[i][j] = i দৈর্ঘ্যে jটি ইউনিক গান দিয়ে প্লেলিস্টের সংখ্যা।
- ট্রানজিশন: নতুন গান যোগ করা বা পুরনো গান রিপিট করা (j > K হলে)।
- মডুলার অ্যারিথমেটিক (add, mul) ব্যবহার করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
typedef long long int lli;
class Solution {
int add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
int mul(lli a, lli b) { return ((a % m) * (b % m)) % m; }
public:
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
