首页 > 代码库 > UVA - 1485 Permutation Counting

UVA - 1485 Permutation Counting

2024-07-19 02:50:54   222人阅读

Description

Download as PDF

Given a permutation a1, a2,...aN of{1, 2,..., N}, we define its E-value as the amount of elements where ai >i. For example, the E-value of permutation{1, 3, 2, 4} is 1, while the E-value of{4, 3, 2, 1} is 2. You are requested to find how many permutations of{1, 2,..., N} whose E-value is exactlyk.

Input

There are several test cases, and one line for each case, which contains two integers,N and k. (1$ \le$N$ \le$1000, 0$ \le$k$ \le$N).

Output

Output one line for each case. For the answer may be quite huge, you need to output the answer module 1,000,000,007.


Explanation for the sample:

There is only one permutation with E-value 0:{1, 2, 3}, and there are four permutations with E-value 1: {1, 3, 2}, {2, 1, 3}, {3, 1, 2}, {3, 2, 1}

Sample Input

30 
31

Sample Output

1 
4
题意：给定一个1-n的排列，满足ai > i的下标i的个数称为此排列的E值，给定整数n和k，求E值恰好为k的排列个数。思路：先写出转移方程: dp[i][j] = (j+1)*dp[i-1][j] + (i-j)*dp[i-1][j-1]，我们拿第i个考虑，如果之前有dp[i-1][j]的话，拿它去和那些满足条件的下标换的话，因为第i个数是最大的，所以此时满足的个数是不变的；如果是dp[i-1][j-1]的话，那么我们去和那些((i-1)-(j-1))不满足的换的话满足的个数会+1。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1010;
const ll mod =  1000000007;

ll dp[maxn][maxn];
int n, k;

void init() {
	for (int i = 1; i < maxn; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < i; j++)
			dp[i][j] = ((j+1)*dp[i-1][j] + (i-j)*dp[i-1][j-1]) % mod;
	}
}

int main() {
	init();
	while (scanf("%d%d", &n, &k) != EOF) {
		printf("%lld\n", dp[n][k]);
	}
	return 0;
}


UVA - 1485 Permutation Counting


联系
我们