题解 UVA1485 【Permutation Counting】

状态定义：f（n，k）为n个元素，E-value为k的排列个数；

转移方程：f（n，k）= f（n-1，k）* 1 放在最后

    + f（n-1，k）* k   放在最后和ai>i的元素交换

               + f（n-1，k-1）*（n-k） 放在最后和ai≤i的元素交换

void solve() {
    rep(i, 1, 1000) {
        f[i][0] = 1;
        rep(j, 1, 1000) 
            f[i][j] = (f[i - 1][j] * (j + 1) + f[i - 1][j - 1] * (i - j)) % Mod;
    }
    while (~scanf("%d%d", &N, &k)) {
        printf("%lld\n", f[N][k]);
    }
}