Permutation Counting

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1633    Accepted Submission(s): 845 Problem Description 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 exactly k.   Input There are several test cases, and one line for each case, which contains two integers, N and k. (1 <= N <= 1000, 0 <= k <= 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.   Sample Input 3 0 3 1   Sample Output 1 4 Hint 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}   Source 2010 Asia Regional Harbin  

大体题意：

有一个1，2，3，，，n 的数组，他的每一个排列都有一个E值，E值的大小是  是元素 a[i] > i 的个数。求解1~n 的数组排列E值等于m 的个数！

思路：

比赛时看暴力数据看了很久，一直看到最后，好像有点规律，结果错在long long  溢出了。。哎~

在借鉴了学长的博客后，感觉想的好简单，当时就是死活想不到= =！ 还需更加努力啊！

令dp[i][j]表示长度为i 的数组， E值为j的答案数！

既然推到dp[i][j]了 ，那么dp[i-1][j]也就知道了， 

他可以由i-1 数组 的情况推过来，

总共三种情况：

1.  把新增的数放在最后，E值不变  ans += dp[i-1][j]

2.把 新增的数和满足条件的数交换，那么E值依旧不变！  ans += dp[i-1][j] * j;

3. 把新增的数和不满足的数交换，那么E值加1 ，ans +=( i-1-(j-1)) * dp[i-1][j-1];

坑：

转移方程时会有乘法，会溢出int，注意一下！

在一个要记得取模 = = ！ 做的太着急  差点忘了。。。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1000 + 10; typedef long long ll; ll dp[maxn][maxn]; const int mod = 1000000007; void init(){ dp[1][0] = 1; dp[1][1] = 0; for (int i = 2; i < maxn; ++i){ dp[i][0] = 1; for (int j = 1; j <= i; ++j){ dp[i][j] = ((dp[i-1][j]%mod) + ((j*dp[i-1][j])%mod) + ((i-j)*dp[i-1][j-1])%mod)%mod; } } } int main(){ int n,m; init(); while(scanf("%d %d",&n,&m) == 2){ printf("%I64d\n",dp[n][m]); } return 0; }