H - RPG的错排
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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
1 1
Sample Input
1 2 0
Sample Output
1 1
________________
考察错排
学习递推思想，要考虑对于第n个数放到第k个位置的时候，
第K个数放在第n位和不是第n位两个情况。
通过百度百科和其他博客学习了一下递推的正确推导方式，进一步加深了理解，大概能明白递推应该从什么样的角度思考了 。
以往总是把递推想太复杂了，光想推导着数学上的通项公式之类的……启示如果正确理解递推思想，递推起来不是很难。
代码如下 :
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std ;
long long int cuopai[30];
void init_cuopai( int n )
{
cuopai[0] = 1 ; // 这是特殊情况,下面会提到.
cuopai[1] = 0; // 这里一开始被卡了一下 ,以为是1的.
cuopai[2] =1;
for( int i = 3 ; i <= n ; i++)
cuopai[i]= (i-1)*(cuopai[i-1] + cuopai[i-2] ) ;
return ;
}
long long int zuhe( int m , int n ) // 从m个数取n 组合
{
long long int ans = 1 ;
for( int i = 1 ; i <= n ; i++)
ans= ans*( m - i + 1 ) / i ;
return ans ;
}
int main()
{
int n ;
init_cuopai(25);
while( cin >> n )
{ if( n == 0 ) break ;
long long int ans=0;
for( int i = 0 ; i <= n/2 ; i++)
{
ans+= zuhe(n,i)*cuopai[i] ;
//他让求正确的答案有多少组,那么也就是0个错排
//1个错排,一直到n/2都错排的数量就好了，需要考虑的是，全部正确也是答案，所以特判
// 0个错排是1
}
cout<< ans << endl ;
}
return 0 ;
}
原文：http://www.cnblogs.com/xiekeyi98/p/6280298.html