博客

【题意】N封信，全部装错信封，一共有几种装错的方式？

【错排公式】F[n]=(n-1)*F[n-1]+(n-1)*F[n-2]

【思路】考虑n封信全部装错的情况，把n封信从1到n编号，考虑n号信封里装的是k号信封的信，而n号信封里的信装在m号信封里。根据k与m是否相等来分成两种情况讨论。

1.若k不等于m，有（n-1）*f[n-1]种

2.若k等于m，有（n-1）*f[n-2]种

#include<iostream>
#include<cstring>
#include<vector>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
#define maxi 0x3f3f3f3f
int f[101];
int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	f[1]=0;f[2]=1;
	for(int i=3;i<=n;i++)
	{
		f[i]=(n-1)*f[n-1]+(n-1)*f[n-2];// 有名的错排公式
	}
	cout<<f[n]<<endl;
	return 0;
}