C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2020-10-31

#include<bits/stdc++.h>
using namespace std;
long int mod=1000000007;
int main()
{
    int n,m,p;
    cin>>n>>m>>p;
    //cout<<n<<m<<p;
    long long int a[101][101];
    //long long int res=1;
    a[0][0]=1;//a[n][p]n首歌填满P个位置
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=p;j++)//p>=n
        {
            if(j>i&&i>m)//p>n,从之前的位置选一首有i*a[i][j-1]种方法,并且间隔中的歌已经不能选了所以*(i-m)不乘i
            {
                a[i][j]+=a[i][j-1]*(i-m);
            }
            a[i][j]+=a[i-1][j-1]*i;//p==n直接阶乘
            
            if(a[i][j]>=mod)//比每一步都mod省时间
            {
                a[i][j]%=mod;
            }
        }
    }
    //res=a[n][p]%mod;
    cout<<a[n][p];
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 468KB, 提交时间: 2020-07-14

/*#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N,M,P;
    cin>>N>>M>>P;
    vector<long long> num(P);
    num[0]=N;
    for(int i=1;i<N;++i)
    {
        num[i]=num[i-1]*(N-i);
        num[i]=num[i]%1000000007;
    }
    for(int i=N;i<P;++i)
    {
        num[i]=num[i-1]*(N-M);
        num[i]=num[i]%1000000007;
    }
    cout<<num[P-1]<<endl;
    return 0;
}*/

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int mod = 1000000007;
int n, m, p;
long long f[maxn][maxn];
int main(){
    int m,n,p;
    cin>> n >> m >> p;
    f[0][0]=1;    //f[n][p] 表示用n首歌，填满p个位置的方法数量
    for(int i=1;i<=n;i++){
        for(int j=i;j<=p;j++){
            //在p>n情况中，在第p位置填入一个在第p位置之前已经填写过的歌曲
            if(j>i && i>m) f[i][j] += (i-m)*f[i][j-1];
            //在p==n的情况中，有n的阶乘种方法填满所有p个位置
            f[i][j]+=f[i-1][j-1]*i;//diff
            if(f[i][j] >= mod)f[i][j] %= mod;
        }
    }
    cout<<f[n][p];
  
    return 0;
}