题解

这是著名的错排问题，设 D(n) 表示n封信全装错的情况，根据题意，有：

$$\begin{equation*} \begin{cases} D(0) = 1\\ D(1) = 0\\ D(2) = 1\\ D(3) = 2\\ D(4) = 9\\ \cdots \end{cases} \end{equation*}$$

那么，由递推可得：

$$\begin{equation*} D(n)= \begin{cases} 1, &n=0\\ 0, &n=1\\ (n-1)\cdot(D(n-1)+D(n-2)),&n\geq2 \end{cases} \end{equation*}$$

所以，可以写出递推代码：

#include<iostream>
using namespace std;
long long dp[23]={1,0};
int main(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)dp[i]=(dp[i-1]+dp[i-2])*(i-1);
    cout<<dp[n]<<endl;
    return 0;
}

或者：

#include<iostream>
using namespace std;
long long a=1,b=0,c;
int main(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        c=(a+b)*(i-1);
        a=b,b=c;
    }
    cout<<c<<endl;
    return 0;
}