HDU 3625 Examining the Rooms
2024-10-18 20:21:12
题目大意:有n个房间,n!个钥匙,在房间中,最多可以破k扇门,然后得到其中的钥匙,去开其它的门,但是第一扇门不可以破开,求可以打开所有门的概率。
题解:首先,建立这样的一个模型,题目相当于给出一个图,求形成1--K个环的可能性有多大。但是节点1不可以形成子环。那么首先,n个点形成1--k个环就是第一类斯特灵数的定义,但是该如何处理1的问题呢,既然算起来比较麻烦,那么正难则反,减去节点1成为自环的情况就可以了。第一类斯特林公式:S(m,n)=(m-1)*S(m-1,n)+S(m-1,n-1)。
#include <iostream>
#include <cstdio>
using namespace std;
long long ans[][],f[];
int main()
{
int t,n,k;
ans[][]=;
f[]=f[]=;
for(int i=; i<; i++)
{
for(int j=; j<=i; j++)
ans[i][j]=ans[i-][j-]+(i-)*ans[i-][j];
f[i]=f[i-]*i;
}
cin>>t;
while (t-- && cin>>n>>k)
{
long long sum = ;
for (int i = ;i <= k;i++)
sum += ans[n][i] - ans[n-][i-];
printf("%.4lf\n",(double)sum/f[n]);
}
return ;
}
最新文章
- PHP Socket实现websocket(一)基本函数介绍
- cpp blog上面看到一哥们写的 下拉列表
- Xcode 8 打包上线 iTunes Connect 找不到构建版本
- ***iOS 项目的目录结构能看出你的开发经验
- php递归方法实现无限分类实例
- Scala IDE for Eclipse的下载、安装和WordCount的初步使用(本地模式和集群模式)
- phpstudy虚拟主机配置
- UVA - 1347 Tour(DP + 双调旅行商问题)
- link 和 @important 的区别
- Spring框架学习笔记(9)——Spring对JDBC的支持
- mysql基础篇 - 其他基本操作
- 彻底搞懂shell的高级I/O重定向
- Spring学习笔记3——使用注解的方式完成注入对象中的效果
- <;发条游戏设计>;粗翻——第一部分 理论(一)
- pip的常用命令
- JMETER content-type增加
- CSU 1857 Crash and Go(relians)(模拟)
- Codeforces 1043 F - Make It One
- python 自然语言处理库https://www.nltk.org/nltk_data/
- scala中Map和Set
热门文章
- 原生js封装table表格操作,获取任意行列td,任意单行单列方法
- <;a>;元素生成多个<;a>;的问题,元素标签结尾影响
- nodejs:注册登录session出错以及连接Mongodb数据库时Error connecting to database解决方案
- JS笔记 入门第二
- 无法打开 configsource 文件
- 激活工具 – Microsoft Toolkit 2.4.7
- CSSBox - Java HTML rendering engine
- iso-开发基础知识-5-适配器
- java程序错误类型及异常处理
- MySQL性能调优的方法