Posted on 2010-08-06 16:00
MiYu 阅读(702)
评论(0) 编辑 收藏 引用 所属分类:
ACM ( 数论 ) 、
ACM ( 组合 )
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2068
题目描述:
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输入结束。
Sample Input
1
2
0
Sample Output
1
1
很明显的 错排 + 排列组合 的题目. 更多错排资料请点击 --> << 错排公式 >>
要猜对一半或一半以上, 那么就是从给出的 n 个人中 取出 小于或等于 n / 2 的人进行错排 ,
因为题目问的是顺利通关的所有解, 所以最后需要累加 0 -> n / 2 的错排方法.
错排公式 :
F ( n ) = ( n - 1 ) * ( F(n-1) + F ( n - 2 ) ) 代码如下 :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include <stdio.h>
typedef long long int64;
int64 Com ( int n, int m ) // 取 Cn m 的 组合数
{
if ( m == 0 )
{
return 1;
}
int64 up = 1,down = 1;
for ( int i = 0; i < m; ++ i )
{
up *= n - i;
down *= i + 1;
}
return up / down;
}
int64 F[14] = { 0, 0, 1, 2 };
void setNum ()
{
for ( int i = 4; i < 14; ++ i )
{
F[i] = ( i - 1 ) * ( F[ i - 1 ] + F[ i - 2 ] );
}
}
int main ()
{
int N;
int64 sum;
setNum ();
while ( scanf("%d", &N), N )
{
sum = 1;
for ( int i = N / 2; i >= 0; -- i )
{
sum += Com ( N , i ) * F[i]; // 从N中取i 个人 的错排数
}
printf("%I64d\n", sum );
}
}