RePorridge

Nothing change but our heart

HDU 2068 RPG的错排

RPG的错排
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5666 Accepted Submission(s): 2325

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+1开始，偶数就从n/2开始，一直循环到n.

假设猜对s个，没猜对t个，其中t = n-s。 组数为C（n,s)*剩余t个人全部没猜中的所有情况。剩余t个人全部没有猜中就是全错位排列

百度一下可知道其递推公式为 f(n)=nf(n-1)+(-1)^(n-2) 又知道 1个元素没有全错位排列，2个元素的全错位排列有1种，3个元素的全错位排列有2种，4个元素的全错位排列有9种，5个元素的全错位排列有44种。

于是可以用for循环递推到13

HDU2068.cpp

posted on 2013-08-31 19:34 Porridge 阅读(532) 评论(0)  编辑 收藏 引用 所属分类: HDU题解


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

<2024年12月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜