解题思路

这是一个动态规划问题，需要计算满足以下条件的播放列表数量：

  1. 首歌要全部播放至少一次
  2. 总共播放 次
  3. 相同歌曲之间至少间隔 首其他歌曲

使用动态规划：

  • 状态定义： 表示用 首歌填满 个位置的方案数
  • 状态转移：
    1. 当 且 时： // 从之前选过的歌中选择，需要满足间隔条件
    2. // 选择一首新歌

代码

#include <iostream>
using namespace std;

const int MOD = 1000000007;
const int MAXN = 101;

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    
    long long dp[MAXN][MAXN] = {0};
    dp[0][0] = 1;  // 初始状态
    
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= p; j++) {
            // 选择新歌
            dp[i][j] = (dp[i][j] + dp[i-1][j-1] * i) % MOD;
            
            // 从之前的歌中选择（需要满足间隔条件）
            if (j > i && i > m) {
                dp[i][j] = (dp[i][j] + dp[i][j-1] * (i-m)) % MOD;
            }
        }
    }
    
    cout << dp[n][p] << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 1000000007;
    private static final int MAXN = 101;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        
        long[][] dp = new long[MAXN][MAXN];
        dp[0][0] = 1;  // 初始状态
        
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= p; j++) {
                // 选择新歌
                dp[i][j] = (dp[i][j] + dp[i-1][j-1] * i) % MOD;
                
                // 从之前的歌中选择（需要满足间隔条件）
                if (j > i && i > m) {
                    dp[i][j] = (dp[i][j] + dp[i][j-1] * (i-m)) % MOD;
                }
            }
        }
        
        System.out.println(dp[n][p]);
        sc.close();
    }
}

MOD = 1000000007
MAXN = 101

# 读取输入
n, m, p = map(int, input().split())

# 初始化dp数组
dp = [[0] * MAXN for _ in range(MAXN)]
dp[0][0] = 1  # 初始状态

# 动态规划过程
for i in range(1, n + 1):
    for j in range(i, p + 1):
        # 选择新歌
        dp[i][j] = (dp[i][j] + dp[i-1][j-1] * i) % MOD
        
        # 从之前的歌中选择（需要满足间隔条件）
        if j > i and i > m:
            dp[i][j] = (dp[i][j] + dp[i][j-1] * (i-m)) % MOD

# 输出结果
print(dp[n][p])

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，其中 为歌曲数量， 为播放次数
  • 空间复杂度：，用于存储 数组