官方题解

【算法分析】

$a_i$ 表示 $i$ 封信封都装错的方案数，初始化：
初始条件：1封信都装错的方案数为0 $a_1$ = 0
2封信都装错的方案数为1 $a_2$ = 1

当 $i$ 大于等于 $3$，递推式为:$a[i] = (i - 1) * (a[i - 2] + a[i - 1])$

【参考代码】

#include<iostream>
using namespace std;

const int N = 30;
long long a[N];

int main() {
	int n;
	cin >> n;
	a[1] = 0; //初始条件：1封信都装错的方案数为0 
	a[2] = 1; //初始条件：2封信都装错的方案数为1
	for (int i = 3; i <= n; i++) {
		a[i] = (i - 1) * (a[i - 2] + a[i - 1]); //递推式 
	}
	cout << a[n]; //输出把n封信都装错的方案数 
	return 0;
}

【时间复杂度】

$O(n)$

【预计得分】

$100pts$