HDUOJ-----2068RPG的错排
2024-10-19 09:33:33
RPG的错排
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6173 Accepted Submission(s): 2508
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
Author
Rabbit
Source
错排公式 fn=(n-1)*(fn-1+fn-2);
此题是错排公式的一个扩展,就是第K错牌的和...
特别要注意算法的格式。。。
这里介绍一下比较规范的组合数的求解
/*@coder 龚细军*/ int cm( int n ,int c)
{
//先比较 c=min{n-c,c}
if(*c>n) c=n-c; //由于cm(n,c)==cm(n,n-c);
int i,j,ret=;
for(i=,j=;i<n;i++)
{
ret*=(n-i);
while(j<=c&&(j%c==))
{
ret/=j;
j++;
}
}
return ret;
} //时间复杂度0(n*c)
此题的代码。。。。简答了啦。。
#include<stdio.h>
int work(int n,int c) /*组合数求c(n,c)*/
{
if(n<*c) c=n-c; //c(n,c)=c(n,n-c)
int i,j,s=;
for(i=,j=;i<c;i++)
{
s*=(n-i); //精简一下避免出现超出int型
for( ; j<=c&&s%j==;++j) s/=j;
}
return s;
}
int main()
{
int i,n;;
_int64 sav[]={,,},ans;
for(i=;i<;i++)
sav[i]+=(i-)*(sav[i-]+sav[i-]);
while(scanf("%d",&n),n)
{
ans=;
for(i=(n+)/;i<=n;i++)
{
ans+=work(n,i)*sav[n-i];
}
printf("%I64d\n",ans);
}
return ;
}
最新文章
- 关于linux下DB2创建数据库报错问题
- CSS 文字阴影(text-shadow)怎么用
- MyEclipse2015 编写js报 &#39;Calculating completion proposals..&#39; has encountered a problem.
- CentOS 6.5 下安装 Redis 2.8.7(转)
- asp.net gridview中增加单击单元格事件
- linux中cat、more、less、tail、head命令
- 定制样式插入到ueditor
- C++11于once_flag,call_once分析的实现
- 如何安装ArchLinux
- mybatis注解开发,动态sql
- bzoj千题计划288:bzoj1876: [SDOI2009]SuperGCD
- 【BZOJ3506】【Cqoi2014】排序机械臂
- centos7设置httpd
- python判断两个文件是否相同
- Testlink1.9.17使用方法(第十章 关键词使用)
- HDFS 上文件块的副本数设置
- MySQL笔记(3)---文件
- zabbix LLD 自定义脚本
- WinForm—串口通讯
- php switch case的";bug";
热门文章
- AndEngine中文文档下载地址
- cocos2d js ScrollView的使用方法
- Objective-C:NSMutableString类的常见操作
- 第二章 mybatis使用注解实现in查询(mysql)
- Hello World with Ant
- javascript制作公式编辑器,函数编辑器和图形绘制
- 一个常见下拉菜单的样式:一体化小三角(纯css手写解决)
- POJ 1564 Sum It Up (DFS+剪枝)
- google/protobuf/releases/tag/v3.4.0 下载
- C# ftp ListFilesOnServer