2023-06-04：你的音乐播放器里有 N 首不同的歌， 在旅途中，你的旅伴想要听 L 首歌（不一定不同
46 / 0 / 创建于 10个月前
moonfdd 的个人博客
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数组。在该函数中先将FAC[0]和INV[0]赋值为1，然后使用循环计算FAC[i]（i从1到LIMIT）的值，并使用费马小定理倒推计算出INV[i]（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乘以FAC[n]、INV[i]、INV[n-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;
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：