5. 不等式数列

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

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

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

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

示例1

输入例子：
5 2
输出例子：
66

我们要求的是$1\sim n1\backslash sim\; n$的所有排列中，满足$kk$个小于号的排列的数量。

考虑动态规划，既然求的是$1\sim n1\backslash sim\; n$的所有排列中，满足$kk$个小于号的排列数量，那么就有$1\sim i1\; \backslash sim\; i$的所有排列中，满足$kk$个小于号的排列数量。

1. 定义：$dp[i][j]dp[i][j]$表示$1\sim i1\; \backslash sim\; i$的所有排列中，满足$kk$个小于号的排列数量
2. 确定递推公式：$dp[i][j]=dp[i-1][j-1]\ast (i-j)+dp[i-1][j]\ast (j+1)dp[i][j]\; =\; dp[i-1][j-1]\; *\; (i-j)\; +\; dp[i-1][j]\; *\; (j+1)$ 见下图

3. 初始化：见下图，只需要初始化一行一列即可。$dp[i][0]dp[i][0]$就是没有<，那么只能是降序，只有一种情况。
4. 根据递推公式推演一遍，验证正确性。并且从下图的推演中可以看出，我们只用得到左半三角，可以节省空间。

package main

import (
    "fmt"
)

func main() {
    var n, k int
    fmt.Scan(&n, &k)

    dp := make([][]int, n + 1)
    for i := 0; i < n + 1; i ++ {
        dp[i] = make([]int, i + 2)
    }

    for i := 0; i < n + 1; i ++ {
        dp[i][0] = 1
    }

    for i := 1; i < n + 1; i ++ {
        for j := 1; j < i + 1; j ++ {
            dp[i][j] = (((dp[i-1][j] % 2017) * (j + 1) % 2017 ) % 2017 + (dp[i - 1][j - 1] % 2017 * (i - j) % 2017) % 2017)% 2017
        }
    }
    fmt.Println(dp[n][k])
}