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

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

时间：2023-06-04 20:35:42浏览次数：65  
标签：cur int INV 2023 int64 ans 旅伴 每首歌 MOD

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

在这里插入图片描述

标签：cur,int,INV,2023,int64,ans,旅伴,每首歌,MOD
From： https://www.cnblogs.com/moonfdd/p/17456220.html

相关文章

  • 2023-06-04：你的音乐播放器里有 N 首不同的歌， 在旅途中，你的旅伴想要听 L 首歌（不一定不
    2023-06-04：你的音乐播放器里有N首不同的歌，在旅途中，你的旅伴想要听L首歌（不一定不同，即，允许歌曲重复，请你为她按如下规则创建一个播放列表，每首歌至少播放一次，一首歌只有在其他K首歌播放完之后才能再次播放。返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模10^9......
  • 2023_6_2
    昨天忘记保存了，痛失笔记https://blog.csdn.net/zhaohongfei_358/article/details/122797190标量、向量和张量之间的区别：https://blog.csdn.net/weixin_44010756/article/details/119940429标量：一个单独的数向量：一列数，张量：给予向量和矩阵的推广，标量可视为零阶张量，矢量是一阶......
  • 2023年中总结--没啥思路
    回了两趟家？ 清明，五一 学雅思，背单词，花了很大精力，还是达不到90%的正确率  得与失  5月MSI比赛，看了 BLGVSGG ； BLGVST1; JDGVST1; BLG VSG2   4月 读书《万万没想到》《如何阅读一本书》电影《何以为家》《驭风男孩》《黑洞频率》  ......
  • C/C++数据结构设计题[2023-06-04]
    C/C++数据结构设计题[2023-06-04]停车场模拟管理程序的设计与实现1．设计目的理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。2．问题描述设停车场只有一个可停放几辆汽车的狭长通道，只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺......
  • 2023年6月3日,枚举，枚举底层实现
    1.枚举1.枚举枚举是一种受限制的类，枚举第一行必须创建对象，枚举不能显示继承父类（枚举没有父类），所有的自定义枚举类默认继承Enum类packagecom.wz.enum01;publicenumSeason{spring("春天","春雨绵绵"),summer("夏天","烈日炎炎"),autumn("秋天","硕果累累"),......
  • 【闲话】2023.06.04
    简单记一下最近的事。期末进步了，虽然还是不满意吧。尤其是物理和语文。但是！我英语小作文满昏！没考过这样的，孩子乐傻了。高考放高考假好耶。但是六点半的早读是一败笔。祝学长学姐高考顺利！后面忘了但是塞尔达传说：王国之泪是……......
  • 2023校赛补题
    端水大师#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintread(){intx=0,o=1;charch=getchar();while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')o=-1,ch=get......
  • 2023年第三届陕西省大学生网络安全技能大赛-pwn-may be all
    2023年第三届陕西省大学生网络安全技能大赛-pwn-maybeall?前言校队丢了两道题给我，看了看都是简单题，简单做了做。不知道具体叫什么名，就用pwn1、pwn2代替了。pwn1简单的格式化字符串泄露，除了远程docker的变量偏移不一样之外，没什么好说的。（出题人的docker可能有问题#!/usr/bin......
  • ansible实战-2023
    环境信息：cat/etc/ansible/hosts[webserver]192.168.31.18ansible_ssh_user=rootansible_ssh_pass=123456http_port=815testvar=31.18mysql_port=3309[dbserver]192.168.31.19ansible_ssh_user=rootansible_ssh_pass=123456http_port=816testvar=31.19mysql_port=3310......
  • 2023.5 codeforces 杂题选做
    2023.5codeforces杂题选做E.Location\(n\le5\times10^4\)的范围，并且区间赋值、区间维护最值，可以考虑分块。然后对于散块的修改可以直接暴力，对于整块，由于\(b_i\)值不变，\(a_i\)值只有一个，思考如何快速求。由于\(\dfrac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}=\d......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99