【题解】A. 错排问题

递推T1

题面（可从下方链接跳转看原题题面）：

求多少个 n 个数的排列 ，满足对于任意的 i(1≤i≤n)，有 Ai≠i 。

题目传送门

序言 & 结论：

这是一道经典的题目，可以先记一下这个结论，设 f[n] 表示有 n 个数错排

f[n]=(n-1)*(f[n-1]+f[n-2])

推理过程：

• f[n] 状态的设置是显然的（无需多言）
• 边界状态有 f[1]=0，f[2]=1
• 考虑转移

首先，我们从 n 个数中取出一个数 x，并且 x 占据了 y 的位置，对于 y 进行分类讨论

1. 若 y 占据了 x 的位置
   则问题转化为计数剩余 n-2 个数的错排问题，即 f[n-2]
2. 若 y 占据了一个非 x 的新的位置
   则问题与 x 无关，转化为不包含 x 而包含 y 的 n-1 个数的错排问题，即 f[n-1]

由加法原理，对于任意一个固定位置的x，都有方案数=f[n-1]+f[n-2]
考虑到x的位置是从除 x 本身的 n-1 个位置中任意选取的，故 f[n]=(n-1)*(f[n-1]+f[n-2])

细节处理：

• 观察数据范围 n≤20，f[n] 是会爆 int 的（别问我是怎么知道的，反正是见到祖宗了 qwq）
• 注意边界状态赋值 f[1]=0，f[2]=1

代码：

讲的很详细了，注释就不写了

#include<iostream>
#define ll long long
using namespace std;
const int maxn=20+10;
ll n,f[maxn];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	f[1]=0;
	f[2]=1;
	for(int i=3;i<=20;i++){
		f[i]=(i-1)*(f[i-1]+f[i-2]);
	}
	/*
	for(int i=1;i<=20;i++){
		cout<<f[i]<<" ";
	}
	*/
	cout<<f[n]<<endl;
	return 0;
}

完结撒花！