题目地址：
https://www.luogu.com.cn/problem/P1595
题目描述：
某人写了
n
n
n
封信和
n
n
n
个信封，如果所有的信都装错了信封，求所有信都装错信封共有多少种不同情况。
输入格式：
一个信封数
n
n
n
，保证
n
≤
20
n \le 20
n
≤
20
。
输出格式：
一个整数，代表有多少种情况。
数据范围：
对于
100
%
100 \%
100%
的数据，
1
≤
n
≤
20
1 \le n \le 20
1
≤
n
≤
20
。
设
f
[
n
]
f[n]
f
[
n
]
是有
n
n
n
个信封的时候的错排数，则
f
[
1
]
=
0
,
f
[
2
]
=
1
f[1]=0, f[2]=1
f
[
1
]
=
0
,
f
[
2
]
=
1
。考虑
f
[
n
]
f[n]
f
[
n
]
，分步骤做，先将第
1
1
1
个信封放在第
k
k
k
个位置，那么有
n
−
1
n-1
n
−
1
种放法（不能放
1
1
1
号位，别的位置都可以），接下来考虑第
k
k
k
个信封放在了哪儿，第一种情况，它可以放在
1
1
1
号位，那么剩余位置是
n
−
2
n-2
n
−
2
个元素的错排，方案数为
f
[
n
−
2
]
f[n-2]
f
[
n
−
2
]
；第二种情况，它可以放在除了
1
1
1
号位以外的位置，那么可以将这个
k
k
k
号信封也视为
1
1
1
号信封，则方案数为
n
−
1
n-1
n
−
1
个元素的错排，即
f
[
n
−
1
]
f[n-1]
f
[
n
−
1
]
；由加法原理，固定
k
k
k
后，方案数为
f
[
n
−
2
]
+
f
[
n
−
1
]
f[n-2]+f[n-1]
f
[
n
−
2
]
+
f
[
n
−
1
]
，再由乘法原理，
f
[
n
]
=
(
n
−
1
)
(
f
[
n
−
2
]
+
f
[
n
−
1
]
)
f[n]=(n-1)(f[n-2]+f[n-1])
f
[
n
]
=
(
n
−
1
)
(
f
[
n
−
2
]
+
f
[
n
−
1
])
代码如下：
#include <iostream>
using namespace std;
const int N = 30;
int n;
long f[N];
int main() {
scanf("%d", &n);
f[1] = 0, f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
printf("%ld\n", f[n]);
}
时空复杂度
O
(
n
)
O(n)
O
(
n
)
。