จำนวนรายการเพลงใน 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,

• return ((a mod m) - (b mod m) + m) mod m

• กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,

• กลับ ((a mod m) * (b mod m)) mod m

• จากวิธีหลัก ให้ทำดังนี้ −

• สร้างอาร์เรย์ 2d ขนาดหนึ่ง dp(L + 1) x (N + 1)

• dp[0, 0] :=1

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=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