题意：n封信全部装错的种数

我的理解：ans[n] = n! - c[n][i]*ans[n-i]             (i = 1,2,3......n)。

code：

#include 
     
      using namespace std;int main(){    long long n,ans[21],a[21],c[21][21];    a[0] = 1;    a[1] = 1;    for(int i = 2;i < 21;i ++){        a[i] = i * a[i-1];        //cout << i << " "<< a[i] << endl;    }    for(int i = 1;i < 21;i ++)        for(int j = i;j > 0;j --){            c[i][j] = a[i]/(a[j]*a[i-j]);            //cout << i <<" " << j << "   " << c[i][j] << endl;        }    ans[0] = 1;    ans[1] = 0;    for(int i = 2;i < 21;i ++){        ans[i] = a[i];        for(int j = 1;j <= i;j ++){            ans[i] -= c[i][j] * ans[i-j];        }    }    while(cin >> n){        cout << ans[n] << endl;    }    return 0;}
     

正规：

基本形式：d[1]=0;   d[2]=1

递归式：d[n]= (n-1)*( d[n-1] + d[n-2])

著名的错排公式。

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