不等式数列

链接：https://www.nowcoder.com/questionTerminal/621e433919214a9ba46087dd50f09879
来源：牛客网

度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入描述:

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

 

输出描述:

输出满足条件的排列数,答案对2017取模。

示例1

输入

5 2

输出

66

 

编程思路：DP。

AC code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1001;
int dp[maxn][maxn];
 
int main()
{
    int n,k,i,j;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(i=2;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            dp[i][j]=(dp[i-1][j]*(1+j)+dp[i-1][j-1]*(i-j))%2017;
        }
    }
    cout<<dp[n][k]<<endl;
}