题意：给出数字n，问n的所有的排列中满足Ai>i 数字恰好为 k的排列的个数。

sl : dp

dp【n】【k】 = dp【n-1】【k】*(k+1) + dp【n-1】【k-1】*(n-1-k+1);

 

为什么？ 稍微一想就知道了。

 

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #include <vector>

 5 

using 

namespace std;

 6 

const 

int MAX= 

1000;

 7 

const 

int MOD = 1e9+

7;

 8 typedef 

long 

long LL;

 9 

int dp[MAX][MAX];

10 

int main() {

11     

int n,k;

12     

while(scanf(

"

%d %d

",&n,&k)==

2) {

13         memset(dp,

0,

sizeof(dp));

14         

for(

int i=

1;i<=n;i++) dp[i][

0]=

1;

15         

for(

int i=

1;i<=n;i++) {

16             

for(

int j=

1;j<=i;j++) {

17                 dp[i][j]=((LL)dp[i-

1][j]*(j+

1)+(LL)dp[i-

1][j-

1]*(i-j))%MOD;

18             }

19         }

20         printf(

"

%d\n

",dp[n][k]);

21     }

22     

return 

0;

23 }

24 //dp[n][k]=dp[n-1][k]*(k+1)+dp[n-1][k-1]*(n-1-k+1);