【DP】【Asia - Harbin - 2010/2011】【Permutation Counting】

【題目描述】Given a permutation a₁, a₂,...a_N of {1, 2,..., N}, we define its E-value as the amount of elements where a_i > 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. (1N1000, 0kN).

?

?

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

3 0 
3 1

?

Sample Output

1 
4

【個人體會】一開始在YY能不能找到規律直接能算出答案，然后還打了一個暴力算出了10以內的情況，
后來發現找不出來，于是才回歸正道。聯想到全錯位排列的遞推方式，立馬懂了這題其實就是個DP。

【題目解析】假設我已經求出了N-1個數，其中ai>i為K個的總方案數。那么考慮添加N這個元素進去
，現在N正好放在第N位上面，那么此時是的排列正好屬于DP[N][K],然后將這個元素和之前的ai>i的
元素進行交換，一共是K種交換，得到的方案數都是屬于DP[N][K]，因此DP[N][K]+=DP[N-1][K]*(K+1),
另外一種是將元素N和ai<=i的元素進行交換，這樣的話就會多出1個ai>i的元素（即N這個元素）。因此
DP[N][K]+=DP[N-1][K-1]*(N-1-(K-1)) 

【代碼如下】

#include <iostream>

using namespace std;

typedef long long int64;

const int64 mod = 1000000007;

int64 F[1001][1001], N, K;

int64 Dp(int64 n, int64 k)
{
    if (F[n][k]) return F[n][k];
    if (n == 0 || n == k) return 0;
    if (k == 0) return 1;
    int64 t1 = Dp(n - 1, k) * (k + 1) % mod, t2 = Dp(n - 1, k - 1) * (n - k) % mod;
    int64 tmp = (t1 + t2) % mod;
    F[n][k] = tmp;
    return tmp;
}

int main()
{
    while (cin >> N >> K) cout << Dp(N, K) << endl;
    return 0;
}

?

?