题目链接：uva 1485 - Permutation Counting

题目大意：给定n和k，要求求一个由1~n组成的序列，要求满足ai>i的i刚好有k个的序列种数。

解题思路：dp[j][i]表示长度为i，j个位置满足的情况。

• dp[j+1][i]+=dp[j][i]?(j+1);

  1, (3), (4), 2: 括号位置代表ai>i,既满足位置,此时i = 4， j = 2.

  -> 1, (3), (4), 2, 5 1 种，在最后追加
  -> 1, (5), (4), 2, 5
  1，(3), (5), 2, 4 j 种，与满足的位置交换，因为新追加的数肯定为当前最大的数，所以满足条件的个数不变

  • dp[j+1][i+1]+=dp[j][i]?(i?j);

    -> (5), (3), (4), 2, 1
    -> 1, (3), (4), (5), 2 i-j 种， 与不满足的位置交换。

    #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long ll; const int maxn = 1000; const ll MOD = 1e9+7; int N, K; ll dp[maxn+5][maxn+5]; void init () { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i <= maxn; i++) { for (int j = 0; j <= i; j++) { dp[j][i+1] = (dp[j][i+1] + (j + 1) * dp[j][i]) % MOD; dp[j+1][i+1] = (dp[j+1][i+1] + (i - j) * dp[j][i]) % MOD; } } } int main () { init(); while (scanf("%d%d", &N, &K) == 2) { printf("%lld\n", dp[K][N]); } return 0; }