链家2018链习生招聘考试-编程题二

发表于 | 分类于 ，

题目

描述

小明喜欢在火车旅行的时候用手机听音乐，
他有 N 首歌在手机里，在整个火车途中，他可以听 P 首歌，
所以他想产生一个播放表产生 P 首歌曲，这个播放表的规则是： 
· 每首歌都要至少被播放一次 
· 在两首一样的歌中间，至少有M首其他的歌 
迈克在想有多少种不同的播放表可以产生，
那么给你 N,M,P,你来算一下，
输出结果取1000000007的余数

输入

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

输出

输出结果 mod 1000000007 的余数

Example

Input

1 0 3

Output

1

题解

动态规划

  • 定义 songList(i,j) 为安排到了第 j 首歌时已经用了 i 首不同歌的安排的种类数
  • 当 j>i 时,萝卜多坑少,所以种类数为0
  • 当 j==i 时,当然是全排列 A(n,n)
  • 当 j>m 时就可以出现重复了,有两种安排方法,添加新歌,添加重复歌,所以其值就是这两种情况的和
    • 当 j<=n 时添加重复歌曲的种类为 songList(i-1,j)*(j-m)
    • 当 j>n 时添加重复歌曲的种类为 songList(i-1,j)*(n-m), 因为一共就 n 首歌
  • songList(n,p) 即为所求
  • 可以压缩空间复杂度为O(n)
  • 状态转移方程
1
2
3
songList(i,j) =	|-> 0, j>i
    	    	|-> songList(i-1,j-1)*(n-j+1), j==i
    	    	|-> songList(i-1,j-1)*(n-j+1)+songList(i-1,j)*(min(j,n)-m), j>m
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>

#define ll long long
#define ull unsigned long long
#define inf 1000000007

using namespace std;

ll n,m,p,songList[105];

int main()
{
    while(cin>>n>>m>>p)
    {
        memset(songList,0,sizeof songList);
        songList[0]=1;
        for(ll i=1;i<=p;++i)
        {
            for(ll j=n;j>=0;--j)
            {
                if(j>i)
                    songList[j]=0;
                else if(j==i)
                    songList[j]=songList[j-1]*(n-j+1);
                else if(j>m)
                    songList[j]=songList[j-1]*(n-j+1)+songList[j]*(min(j,n)-m);
                else
                    songList[j]=0;
                if(songList[j]>=inf) songList[j]%=inf;
            }
        }
        cout<<songList[n]<<endl;
    }
}