0920. Number of Music Playlists¶
题目信息¶
- 题号:
0920
- 难度:
Hard
- 主题:
播放列表、组合计数、重复间隔
- 原题:
- 重点:
长度为
goal的列表必须覆盖全部n首不同歌曲;同一首歌再次出现前必须已经播放至少k首其他歌曲
题目重述¶
有 n 首彼此不同的歌曲,需要生成一个恰好包含 goal 次播放的有序列表。每首歌曲必须在列表中至少出现一次,歌曲可以重复播放。
若某首歌曲已经播放过,则它再次出现之前,二者之间必须至少播放 k 首其他歌曲。请返回满足全部条件的不同播放列表数量,并对 10^9 + 7 取模。
1 <= n <= goal <= 100,0 <= k < n。播放位置不同或任一位置所选歌曲不同,就视为不同列表。
自建示例¶
两首歌必须交替播放:
输入:n = 2, goal = 3, k = 1
输出:2
解释:合法列表只有 [1,2,1] 和 [2,1,2]。相同歌曲之间隔着另一首歌,并且两首歌都至少出现一次。
只有一首歌且没有冷却限制:
输入:n = 1, goal = 4, k = 0
输出:1
解释:唯一歌曲必须占据四个播放位置。k 为 0 时可以立即重复,因此只有 [1,1,1,1] 这一种列表。