错排问题

又叫错位排列、重排，即使一个排列所有的元素都不在原来的位置上。

1.信封问题

共有 n 张信和 n 个信封，假设所有信都装错了信封，共有多少种情况？

k 号元素的排列有两种方式：

一是放在第 1 个位置，剩下的 n − 2 个元素进行错排，共有 f ( n − 2 ) 种可能；

二是不放在第 1个位置，这时我们将第 1个位置看作第 k 个位置，于是就形成了包括 k 号元素在内的 n − 1个元素的错排，共有 f ( n − 1 ) 种可能。

所以，k号元素共有 f ( n − 1 ) + f ( n − 2 ) 种可能。

又因为第一号元素有 n − 1 种放法，根据乘法原理。

#include<iostream>
#include<cstdio>

using namespace std;

long long f(long long x)//一定要开long long
{
	if( x == 1 )
		return 0;
	else if( x == 2 )
		return 1;
	else
		return (x-1)*(f(x-1)+f(x-2));
}

int main()
{
	int n;
	cin>>n;
	cout<<f(n);
	return 0;
}