首页 > 试题广场 >

不等式数列

[编程题]不等式数列

热度指数：4040 时间限制：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

输出

算法知识视频讲解

JavaScript

楼西

var ins = readline().split(" ");
var n = parseInt(ins[0]);
var num = parseInt(ins[1]);
function numbers(total, k){
    var arr = [];
    for(var i=0; i<total+1; i++){
        arr[i] = [];
        arr[i][0] = 1;
    }
    for(var j=0; j<k+1; j++){
        arr[0][j] = 0;
    }
    for(var n=1; n<total+1; n++){
        for(var m=1; m<k+1; m++){
            arr[n][m] = (arr[n-1][m-1]*(n-m) + arr[n-1][m]*(m+1))%2017;
        }
    }
    return arr[total][k];
}
print(numbers(n, num));

发表于 2017-11-22 15:28:34 回复(0)

JavaScript

寻壑


	
	
		var readline = require('readline');
	

	
		var rl = readline.createInterface({
	

	
		input: process.stdin,
	

	
		output: process.stdout
	

	
		});
	

	
		var inputs = [];
	

	
		rl.on('line', function(data){
	

	
		inputs = data.split(' ');
	

	
		var result = deal(inputs);
	

	
		console.log(result);
	

	
		num = 0;
	

	
		inputs = [];
	

	
		});
	
// 动态规划算法，两个边界条件：



	// 1. dp[j][0]=1，即全部为大于号的情况



	// 2. dp[j][j-1]=1，即全部为小于号的情况
	
		function deal(arr){
	

	
		var n = +arr[0];
	

	
		var i = +arr[1];
	

	
		var dp = [];
	

	
		for(var j=1;j<=n;j++){
	

	
		dp[j] = new Array(i+1);
	

	
		dp[j][0] = 1;
	

	
		}
	

	
		for(j=2;j<=n;j++){
	

	
		for(var k=1;k<=Math.min(j-1,i);k++){
	

	
		if(k===j-1) dp[j][k] = 1;
	

	
		else dp[j][k] = (dp[j-1][k]*(k+1)+dp[j-1][k-1]*(j-k))%2017;
	

	
		}
	

	
		}
	

	
		return dp[n][i];
	

	
		}