笔试-音乐

发表于 | 更新于

题意

迈克喜欢在火车旅行的时候用手机听音乐，他有N首歌在手机里，在整个火车途中，他可以听P首歌，所以他想产生一个播放表产生P首歌曲，这个播放表的规则是：

  • 每首歌都要至少被播放一次
  • 在两首一样的歌中间，至少有M首其他的歌

迈克在想有多少种不同的播放表可以产生，那么给你N,M,P，你来算一下，输出结果取1000000007的余数。

输入:

输入N,M,P
N范围在1到100
M范围在0到N
P范围在N到100

输出 :

输出结果mod 1000000007的余数
样例输入
1 0 3
样例输出
1
提示
其他样例
1 1 3
0

2 0 3
6

50 5 100
222288991

题解

DP[i][j]表示前 i 首歌共使用了 j 首不同的歌。
考虑第i首歌，如果取前面已经用过的歌，那么可选的歌有（j-m）首歌，如果选用前面没用过的歌，那么可选的歌有（n-j+1）首歌可选。所以

dp[i][j] = dp[i-1][j] * (j-m) + dp[i-1][j-1] * (n-j+1)

，注意int会超出范围。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 105;
const int MOD = 1e9+7;
LL dp[MAX][MAX];

int main(){
    int n,m,p;
    while(cin>>n>>m>>p){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=p;i++){
            dp[i][0] = 0;
        }
        for(int j=1;j<=n;j++){
            dp[0][j] = 0;
        }
        dp[0][0] = 1;
        for(int i=1;i<=p;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = (dp[i-1][j-1]*(n-j+1))%MOD;
                if(j>m) dp[i][j] = (dp[i][j] + (dp[i-1][j]*(j-m))%MOD)%MOD;
            }
        }
//        for(int i=0;i<=p;i++){
//            for(int j=0;j<=n;j++){
//                cout<<dp[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        cout<<dp[p][n]<<endl;
    }
    return 0;
}