#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e3 + 9;
int f[N];
int main() {
  
  
    return 0;
}

这一讲我们来实现错排公式，其实这一讲和菲波那切数列类似，只不过是递推公式不同。

这里我们还是先接收一个整数 n（这里的 n 需要更小）。

请在main()函数中写下：

int n;
cin >> n;

这一步我们只需要初始化数据。

分别表示一封错排的方案数，和两封信错排的方案数。

请在return 0;上面写下：

f[1] = 0;
f[2] = 1;

这一步我们根据递推公式$f[n] = (f[n - 1] + f[n - 2]) \times (n - 1)$进行计算。

请在reurn 0;上面写下：

for (int i = 3; i <= n; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) * (i - 1);
}

这时我们就已经完成了计算，可以输出答案了。

请在return 0;上面写下：

cout << f[n] << endl;

这里我们发现这个公式也可以进行空间优化。

我们依然是先初始化代码。

a 表示一封信错排的方案数，b 表示两封信错排的方案数。

请在return 0;上面写下：

ll a = 0, b = 1, c = 1;

这里我们依然是根据公式 $f[n] = (f[n - 1] + f[n - 2])$ 进行代码的编写。这里的 c 相当于 f[n]。 所以现在的公式是 $c = (a + b)×(n−1)$ 。 计算完 c 的值之后，需要记得更新 a , b 的值。

请在return 0;上面写下：

for (int i = 3; i <= n; ++i) {
    c = (a + b) * (i - 1);
    a = b;
    b = c;
}

最后我们就可以输出优化后代码的答案。我们可以和上面的进行对比看看我们优化的是否正确。

这里输出答案的时候，我们需要注意一个特殊情况。因为当n=1 的时候，我们直接输出 c 答案是错误的。所以我们需要添加一个判断。

这里希望大家知道，无论是现在的递推，还是后面讲到的动态规划，边界的处理都是不容忽视的。

请在return 0;上面写下：

if (n != 1) {
    cout << c << endl;
} else {
    cout << 0 << endl;
}

现在你可运行你的程序了。

可以计算 n = 10 的答案了。

相信这个时候，聪明的你已经学会 错排公式 的实现了。

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e3 + 9;
int f[N];
int main() {
   int n;
   cin >> n;
   f[1]=0;
   f[2]=1;
   for(int i=3; i<=n; i++) {
   	f[i] = (f[i-1]+f[i-2])*(i-1);
   }
   cout << f[n] << endl;
   ll a=0,b=1,c=1;
   for(int i=3; i<=n; i++) {
   	c=(a+b)*(i-1);
   	a=b;
   	b=c;
   }

   if(n!=1) {
   	cout << c << endl;
   } else {
   	cout << 0 <<endl;
   }
   return 0;
}