Problem Description 今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动，做ACM的女生越来越多，我们的野骆驼想都知道她们，可现在有N多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个case,每个case包括一个n，代表有几个女生，（n<=25）, n = 0输入结束。
Output
给出有多少组答案能使他顺利过关。
Sample Input
1
2
0
Sample Output
1
1
Author
Rabbit
Source RPG
专场练习赛
Recommend
lcy
分析：这是一道错排加组合的问题，刚开始我有一种错误的思想：以为对的和错的必须是n/2；其实应该是错误的在0---n/2都可以的。这里需要一个错排公式，f(1)=0;f(2)=1;
f(i)=(i-1)*(f(i-1)+f(i-2));由于数很大得用__int64，，，代码如下：
#include<iostream>
#include<stdio.h>
using namespace std;
__int64 c(int n,int m)
{__int64 up=1;__int64 down=1;for(int i=n;i>n-m;i--) //简单的排列组合，细节{up=up*i;}for(int j=1;j<=m;j++){down=down*j;}return up/down;
}
int main()
{__int64 a[30];int n;a[1]=0;a[2]=1;for(int i=3;i<30;i++) //错排公式a[i]=(i-1)*(a[i-1]+a[i-2]);while(cin>>n){if(n==0)break;__int64 sum=1;for(int i=1;i<=n/2;i++){sum=sum+a[i]*c(n,i);}printf("%I64d\n",sum);}return 0;
}