首页 > 试题广场 >

不等式数列

[编程题]不等式数列

热度指数：4038 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

5 2

输出

算法知识视频讲解

Python

xNazgul

dp的python实现，AC

def permute(n, k):
    cur_d = {i: 1 for i in range(n - k)}
    pre_d = {}
    for j in range(1, k + 1):
        pre_d = cur_d
        cur_d = {0: 1}
        for i in range(1, n - k):
            cur_d[i] = pre_d[i] * (i + 1) + cur_d[i - 1] * (j + 1)
    return cur_d[n - k - 1]

编辑于 2018-04-17 02:11:03 回复(1)

Python

小欣8


	M, N = [int(x) forx in input().split(' ')]



	 



	 



	dp = [[0forj in range(N+1)] fori in range(M+1)]



	 



	fori in range(1, M):



	    dp[i][0] = 1



	fori in range(2, M+1):



	    forj in range(1, N+1):



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



	        dp[i][j] = token % 2017



	print(dp[M][N])