假设我们有一个音乐播放器，其中包含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，
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）的2d数组
dp [0，0]：= 1
对于初始化i：= 1，当i <= L时，更新（将i增加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））
对于初始化j：= 1，当j <= N时，更新（将j增加1），-
返回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