发邮件

发邮件

时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB 判断程序 Standard (来自 小小)

题目描述

NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？

即没有人收到属于自己的邮件。

 

输入描述:

输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。

 

输出描述:

对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。

 

输入例子:

2
3

 

输出例子:

1
2

#include<stdio.h>

int main()
{
	int n,i;
	long long a[25];
	a[2]=1;
	a[3]=2;
	for(i=4;i<=20;i++)
		a[i]=(i-1)*(a[i-1]+a[i-2]);
	while(scanf("%d",&n)!=EOF)
	{
		printf("%lld\n",a[n]);
	}
	return 0;
 } 

ps:数组类型应该是long long,刚开始用的int就错了。。。

假设a放进了B中：分两种情况，

一种情况是b放在A中，有D（n-2）种方法，

另一种情况是b没有放在A中，实际上就是把b,c,d...放进A,C,D...中也就是有D(n-1)放法，而把a放进C,D,E...中有同样的D(n-1) + D(n-2)种放法，所以有n封信就应该有(n-1)[D(n-1) + D(n-2)]种放法。