4.D

题目连接 http://acm.hust.edu.cn/vjudge/contest/125308#problem/

题目大意 n个信封 n封信 要把所有的信都装错信封，求最多有多少种错误的方式。

编号1~n个元素，编号1~n个位置。d[n]代表n个元素，n个位置，错误的所有方式。

1.先放第n个元素，一共有n-1种放法

2.放编号为k的元素，这时有两种情况⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有d(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有d(n-1)种方法；

所以有 d[n]=(n-1)*(d[n-1]+d[n-2] ）；d[1]=0;d[2]=1;

此外虽然1<n<20;但d[20]却很大，要用long long 型（lld)八个字节 19位数。

#include<iostream>
#include<cstdio>
using namespace std;
long long p[25];
void in()
{
    p[1]=0;p[2]=1;
    for(int i=3;i<=20;i++)
    p[i]=(i-1)*(p[i-1]+p[i-2]);

}
int main()
{
    in();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld
",p[n]);
    }
    return 0;
}