网站首页
编程语言
数据库
系统相关
其他分享
编程问答
OCPC2023
2024-08-13
OCPC2023 I. DAG Generation
题目传送门题意给你一种DAG生成方式,问生成两张DAG相同的概率是多少。生成方式为,一开始有\(A,B\)两个集合,A为空集,B中有\(1-n\)每个节点,每次从B中随机取出一个点,然后在A中随机取出一个子集,把子集中的每个点往B中取出的点连一条有向边,然后把取出点放入A。题解我们不妨认为第一次