题意：
问n封信中前m封信全都不是自己应该得到的情况数..
思路：
3种方法：
①. 记忆化搜索..
比如有n个，k个错排的话。总排列数数n!
然后这n!个要减掉不符合题意的
就是k个中1个没有错排，2个没有错排,....k个没有错排
如果k个中1个没有错排的话，就是 C[k][1]*(n-1个中k-1个错排)
f[i]=(i-1)*(f[i-1]+f[i-2])
②. DP..
如果用dp[i][j]表示i个人中前j个人是错排的..
那可以看成i个人中前j个人中某一个人的错排是由4种情况得到的..1st：前j个人中有1个人跟他错排了..而且正好是互换位置了..那就是dp[i-2][j-2]
2ed： 前j个人中1个人跟他错排了..但是不是互换位置的..那就是dp[i-1][j-1]
3rd：后i-j个人中有一个和他错排了..而且正好互换位置了..那就是dp[i-2][j-1]
4th：后i-j个人中有一个人和他错排了..但是不是互换位置..那就是dp[i-1][j]
所以递推公式是：dp[i][j] = (j-1)(dp[i-2][j-2]+dp[i-2][j-1])+(i-j)(dp[i-2][j-1]+dp[i-1][j])
所以只有确定一些基础状态就可以推出后面的状态了..
③. 用组合数学..
在后面的n-m个人中找i(0~n-m)个人与前面的m个人进行错排..所以就是(m+i)个人错排的数量*(n-m个人中选i个人的情况数)
Tips：
错排公式为 f[i] = (i-1)*(f[i-1]+f[i-2])
组合数的公式可以由前两个公式得来..即：C[i][j] = C[i-1][j]+C[i-1][j-1]
因为两个数相乘的时候还是有可能大于整型的..所以应该用long long..
Code：
第三种方法..
1 #include <stdio.h> 2 #include <cstring> 3 #define LL long long 4 5 const int mod = 1000000007; 6 LL C[1010][1010], P[1010]; 7 LL f[1010], dp[1010][15]; 8 9 void init() 10 { 11 memset(dp, 0, sizeof(dp)); 12 C[0][0] = 1; 13 for (int i = 1; i < 1010; ++i) { 14 C[i][0] = C[i][i] = 1; 15 for (int j = 1; j < i; ++j) { 16 C[i][j] = C[i-1][j-1]+C[i-1][j]; 17 C[i][j] %= mod; 18 } 19 } 20 21 P[0] = P[1] = 1; 22 for (int i = 2; i < 1010; ++i) { 23 P[i] = i*P[i-1]; 24 P[i] %= mod; 25 } 26 27 f[0] = f[1] = 0, f[2] = 1; 28 for (int i = 3; i < 1010; ++i) { 29 f[i] = (i-1)*(f[i-1]+f[i-2]); 30 f[i] %= mod; 31 } 32 } 33 34 int main() 35 { 36 int n, m; 37 init(); 38 while (~scanf("%d %d", &n, &m)) { 39 if (dp[n][m] == 0) { 40 for (LL i = 0; i <= n-m; ++i) { 41 dp[n][m] += C[n-m][i]%mod*f[i+m]%mod; 42 dp[n][m] %= mod; 43 } 44 } 45 printf("%lld\n", dp[n][m]%mod); 46 } 47 return 0; 48 }
链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1755