HDU 3664 Permutation Counting (DP)

题意：

问所有的n的排列中有k个ai > i的排列有多少种。

解题思路：

设dp[i][j] 表示i的排列中有j个ak > k的排列个数，状态转移方程就是:

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

对于第i个数 i，如果选择放在当前i这个位置，那么值不变，如果选择放在前面的ai > i 的那个位置上，则值也是不变的，如果选择放在前面的ai  <= i  的位置上，显然值 + 1，所以就很容易推出转移方程。

#include <stdio.h>
typedef __int64 ll;

const int maxn = 1000 + 5;
const int mod = 1000000007;

ll dp[maxn][maxn];

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

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