博客

情景：现在有n封信和n个信封，要求全部放错，问共有多少种做法。

当初接触到这个问题还是在参加数学竞赛的时候，可以用容斥原理解决，没想到我今天还能在打信息竞赛的时候遇到这个问题，现在用递推式介绍一下这道题的解决方法吧！

dp[i]表示前i封信都放错的情况数。

dp [ n ] =（ dp [ n – 1 ] + dp [ n – 2 ] ）*（ n – 1 ）；

下面给出公式推导：

对于1~n封信都放错的情况可以由前n-1封信的放置情况转移过来



，对于前n-1封信的两种情况，一种是全放错了，还有一种是放错了n-2封信，我们可以通过一次交换来使得n封信都放错位置。

对于前一种情况，我们可以从前n-1封放错的信中任选一个与第n封交换位置即可使得n封信都放错位置，而后一种情况中前n-1封信中有一个位置是对的，我们只需要把这个位置放对的信与第n封信交换位置即可使得n封信都放错位置。前一种情况的数目是dp[n-1]*(n-1)，后一种情况是dp[n-2]*(n-1)，所以加起来就得到了公式。

代码实现：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+10;
int dp[N+10];
int main()
{
	dp[0]=1;
	for(int i=1;i<=N;i++)
		dp[i]=(i-1)*(dp[i-1]+dp[i-2]);
	return 0;
}