2023-06-04：你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复，请你为她按如下规则创建一个播放列

原创

福大大架构师每日一题

发布于 2023-06-04 20:13:38

2650

发布于 2023-06-04 20:13:38

文章被收录于专栏：福大大架构师每日一题

2023-06-04：你的音乐播放器里有 N 首不同的歌，

在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复，

请你为她按如下规则创建一个播放列表，

每首歌至少播放一次，

一首歌只有在其他 K 首歌播放完之后才能再次播放。

返回可以满足要求的播放列表的数量。

由于答案可能非常大，请返回它模 10^9 + 7 的结果。

输入：n = 3, goal = 3, k = 1。

输出：6。

答案2023-06-04：

大体步骤如下：

1.定义常量MOD和LIMIT，分别表示模数和阶乘表的最大值。

2.定义全局变量FAC和INV，分别表示阶乘表和阶乘结果的乘法逆元表。

3.编写init函数，用于初始化FAC和INV数组。在该函数中先将FAC0和INV0赋值为1，然后使用循环计算FACi（i从1到LIMIT）的值，并使用费马小定理倒推计算出INVi（i从LIMIT到2）的值。

4.编写power函数，用于计算x的n次方并对MOD取模后的结果。

5.编写numMusicPlaylists函数，根据题目要求计算可以满足要求的播放列表数量。该函数中定义三个int64类型变量：cur、ans和sign。cur用于保存当前循环中需要累加到答案中的部分，ans则是最终结果。sign初始为1，在每次循环结束时将其乘以-1来实现交替相加或相减。

6.numMusicPlaylists函数中使用一个for循环遍历i从0到n-k。在每次循环中，首先计算cur = sign * pow(n-k-i, l-k) % MOD。其中pow函数调用了power函数来计算幂次方。

7.然后将cur乘以FACn、INVi、INVn-k-i并分别对MOD取模，更新cur的值。

8.将cur加到ans中并对MOD取模，最后返回ans的int类型值。

时间复杂度：$O(n^2)$，其中n为歌曲数量。需要计算阶乘表和阶乘结果的乘法逆元表，时间复杂度均为O(n)。在numMusicPlaylists函数中使用了一个for循环，循环次数为n-k，每次循环中调用了power函数，时间复杂度为$O(logMOD)$，然后进行了常数次乘、除和取模运算，时间复杂度为O(1)。因此总时间复杂度为$O(n(n-k)logMOD)=O(n^2*logMOD)$。

空间复杂度：O(n)，主要是用来存储阶乘表和阶乘结果的乘法逆元表。

go完整代码如下：

package main

import "fmt"

const MOD int64 = 1000000007
const LIMIT int = 100

// 阶乘表
var FAC [LIMIT + 1]int64

// 阶乘结果的乘法逆元表
var INV [LIMIT + 1]int64

func init() {
	FAC[0] = 1
	INV[0] = 1
	for i := 1; i <= LIMIT; i++ {
		FAC[i] = (int64(i) * FAC[i-1]) % MOD
	}
	// 费马小定理计算乘法逆元，优化如下
	// 这一块叫：阶乘的逆元倒推
	INV[LIMIT] = power(FAC[LIMIT], int(MOD-2))
	for i := LIMIT; i > 1; i-- {
		INV[i-1] = (int64(i) * INV[i]) % MOD
	}
}

// x的n次方，% mod之后，是多少？
func power(x int64, n int) int64 {
	ans := int64(1)
	for n > 0 {
		if n&1 == 1 {
			ans = (ans * x) % MOD
		}
		x = (x * x) % MOD
		n >>= 1
	}
	return ans
}

func numMusicPlaylists(n int, l int, k int) int {
	var cur, ans, sign int64 = 0, 0, 1
	for i := 0; i <= n-k; i++ {
		// cur ->
		// FAC[n] -> n! % mod 的结果！
		// INV[i] -> i! 的逆元！
		// INV[n - k - i] -> (n - k - i)! 的逆元
		// sign * 1 -> 1
		//      * -1 -> mod - 1
		cur = (sign * power(int64(n-k-i), l-k)) % MOD
		cur = (cur * FAC[n]) % MOD
		cur = (cur * INV[i]) % MOD
		cur = (cur * INV[n-k-i]) % MOD
		ans = (ans + cur) % MOD
		sign *= -1
	}
	return int(ans)
}

func main() {
	n := 3
	goal := 3
	k := 1
	result := numMusicPlaylists(n, goal, k)
	fmt.Println(result)
}

rust完整代码如下：

const MOD: i64 = 1_000_000_007;
const LIMIT: usize = 100;

// 阶乘表
static mut FAC: [i64; LIMIT + 1] = [0; LIMIT + 1];

// 阶乘结果的乘法逆元表
static mut INV: [i64; LIMIT + 1] = [0; LIMIT + 1];

unsafe fn init() {
    INV[0] = 1;
    FAC[0] = 1;
    for i in 1..=LIMIT {
        FAC[i] = ((i as i64) * FAC[i - 1]) % MOD;
    }
    // 费马小定理计算乘法逆元，优化如下
    // 这一块叫：阶乘的逆元倒推
    INV[LIMIT] = power(FAC[LIMIT], (MOD - 2) as i32);
    for i in (2..=LIMIT).rev() {
        INV[i - 1] = ((i as i64) * INV[i]) % MOD;
    }
}

// x的n次方，% mod之后，是多少？
fn power(mut x: i64, mut n: i32) -> i64 {
    let mut ans = 1;
    while n > 0 {
        if (n & 1) == 1 {
            ans = (ans * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    ans
}

pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
    unsafe {
        init();
        let mut cur;
        let mut ans = 0;
        let mut sign = 1;
        for i in 0..=n - k {
            // cur ->
            // FAC[n] -> n! % mod 的结果！
            // INV[i] -> i! 的逆元！
            // INV[n - k - i] -> (n - k - i)! 的逆元
            // sign * 1 -> 1
            //      * -1 -> mod - 1
            cur = (sign * power(n as i64 - k as i64 - i as i64, goal as i32 - k)) % MOD;
            cur = (cur * FAC[n as usize]) % MOD;
            cur = (cur * INV[i as usize]) % MOD;
            cur = (cur * INV[(n - k - i) as usize]) % MOD;
            ans = (ans + cur) % MOD;
            sign *= -1;
        }
        ans as i32
    }
}

fn main() {
    let n = 3;
    let goal = 3;
    let k = 1;
    let result = num_music_playlists(n, goal, k);
    println!("{}", result);
}

c++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;
const int LIMIT = 100;

// 阶乘表
vector<int64_t> fac(LIMIT + 1);

// 阶乘结果的乘法逆元表
vector<int64_t> inv(LIMIT + 1);

int64_t pow2(int64_t x, int n);

void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= LIMIT; i++) {
        fac[i] = ((int64_t)i * fac[i - 1]) % MOD;
    }
    // 费马小定理计算乘法逆元，优化如下
    // 这一块叫：阶乘的逆元倒推
    inv[LIMIT] = pow2(fac[LIMIT], MOD - 2);
    for (int i = LIMIT; i > 1; i--) {
        inv[i - 1] = ((int64_t)i * inv[i]) % MOD;
    }
}

// x的n次方，% mod之后，是多少？
int64_t pow2(int64_t x, int n) {
    int64_t ans = 1;
    while (n > 0) {
        if (n & 1) {
            ans = (ans * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return ans;
}

int numMusicPlaylists(int n, int l, int k) {
    int64_t cur, ans, sign = 1;
    ans = 0;

    for (int i = 0; i <= n - k; ++i, sign = sign == MOD - 1 ? 1 : MOD - 1) {
        // cur ->
        // FAC[n] -> n! % mod 的结果！
        // INV[i] -> i! 的逆元！
        // INV[n - k - i] -> (n - k - i)! 的逆元
        // sign * 1 -> 1
        //      * MOD-1 -> mod - 1
        cur = (sign * pow2(n - k - i, l - k)) % MOD;
        cur = (cur * fac[n]) % MOD;
        cur = (cur * inv[i]) % MOD;
        cur = (cur * inv[n - k - i]) % MOD;
        ans = (ans + cur) % MOD;
    }

    return ans;
}

int main() {
    init();
    int n = 3, goal = 3, k = 1;
    int result = numMusicPlaylists(n, goal, k);
    cout << result << endl;

    return 0;
}

c完整代码如下：

#include <stdio.h>
#include <stdint.h>

#define MOD 1000000007
#define LIMIT 100

// 阶乘表
int64_t fac[LIMIT + 1];

// 阶乘结果的乘法逆元表
int64_t inv[LIMIT + 1];

int64_t pow2(int64_t x, int n);

void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= LIMIT; i++) {
        fac[i] = ((int64_t)i * fac[i - 1]) % MOD;
    }
    // 费马小定理计算乘法逆元，优化如下
    // 这一块叫：阶乘的逆元倒推
    inv[LIMIT] = pow2(fac[LIMIT], MOD - 2);
    for (int i = LIMIT; i > 1; i--) {
        inv[i - 1] = ((int64_t)i * inv[i]) % MOD;
    }
}

// x的n次方，% mod之后，是多少？
int64_t pow2(int64_t x, int n) {
    int64_t ans = 1;
    while (n > 0) {
        if (n & 1) {
            ans = (ans * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return ans;
}

int numMusicPlaylists(int n, int l, int k) {
    int64_t cur, ans, sign = 1;
    ans = 0;

    for (int i = 0; i <= n - k; ++i, sign = sign == MOD - 1 ? 1 : MOD - 1) {
        // cur ->
        // FAC[n] -> n! % mod 的结果！
        // INV[i] -> i! 的逆元！
        // INV[n - k - i] -> (n - k - i)! 的逆元
        // sign * 1 -> 1
        //      * MOD-1 -> mod - 1
        cur = (sign * pow2(n - k - i, l - k)) % MOD;
        cur = (cur * fac[n]) % MOD;
        cur = (cur * inv[i]) % MOD;
        cur = (cur * inv[n - k - i]) % MOD;
        ans = (ans + cur) % MOD;
    }

    return ans;
}

int main() {
    init();
    int n = 3, goal = 3, k = 1;
    int result = numMusicPlaylists(n, goal, k);
    printf("%d\n", result);

    return 0;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

登录后参与评论

0 条评论

热度