题解

思路

算法一：位压缩动态规划

当 $n\le 15$ 时，用二进制集合 mask 表示已经选入播放列表的歌曲，并记录最后一首歌曲的曲风。预处理每个集合的总时长；从一个状态向尚未使用且曲风不同的歌曲转移。

时间复杂度为 $O(2^n n)$，空间复杂度为 $O(2^n)$。

算法二：按曲风分别选择再卷积

只考虑选中了哪些歌曲。对每种曲风分别做 0/1 背包，令 $F_g[k][s]$ 表示从曲风 $g$ 中选择 $k$ 首、总时长为 $s$ 的方案数。显式卷积 $F_2$ 与 $F_3$，再与 $F_1$ 合并。

另一方面，用四维动态规划计算由 $a,b,c$ 个三种曲风符号组成、且相邻符号不同的曲风序列数。最后乘上 $a!b!c!$，把同一曲风中彼此不同的歌曲放入对应位置。

该算法适用于 $n\le25,T\le300$。瓶颈是时长维的显式卷积。

算法三：联合选择动态规划

做法

设 $A[a][s]$ 表示从曲风 1 中选择 $a$ 首、总时长为 $s$ 的方案数。

将另外两种曲风放进同一个背包，设 $B[b][c][s]$ 表示从曲风 2 中选择 $b$ 首、从曲风 3 中选择 $c$ 首，并且总时长为 $s$ 的方案数。这样直接在一次 0/1 背包中完成原先的卷积。

再设 $W[a][b][c][last]$ 为使用三种曲风各 $a,b,c$ 次，最后一种曲风为 last 的合法曲风序列数。从空序列开始，只向不同于 last 的曲风转移。

固定 $(a,b,c)$ 与曲风 1 的时长和 $s$ 后，贡献为

$$A[a][s]\cdot B[b][c][T-s]\cdot W[a][b][c]\cdot a!b!c!.$$

枚举所有状态并求和即可。所有运算均对 $10^9+7$ 取模。

正确性说明

$A$ 和 $B$ 都是标准的 $0/1$ 背包：每首歌曲只转移一次，因此它们分别且不重不漏地统计了三种曲风中选定歌曲数量与总时长的方案。$W$ 的每次转移只追加与末尾曲风不同的符号，所以它恰好统计所有相邻曲风不同的曲风序列。

固定歌曲数量 $(a,b,c)$ 与曲风 1 的时长和 $s$ 后，$A[a][s]B[b][c][T-s]$ 选出总时长恰为 $T$ 的歌曲集合；$W[a][b][c]$ 决定合法的曲风位置序列；$a!b!c!$ 再把同一曲风中彼此不同的歌曲双射到对应位置。三部分选择相互独立，且任意合法播放列表都唯一对应这一组选择，因此对全部状态求和得到且只得到所有合法播放列表。

复杂度

时间复杂度为 $O(n^3T+n^4)$ 的稠密上界；由于三种曲风数量之和为 $n$，实际状态数为对应三个计数维乘积。空间复杂度为 $O(n^2T+n^3)$。