首页 > 弦
开通博客写题解
头像 Bernard5
发表于 2020-05-13 23:04:50
显然我们需要给出所有弦不交的概率P。 先对分子（两两相连且不相交的情况总数）进行推导：其实这和经典题目凸多边形的三角形划分很相似（但我也没有做过）。易知 时有1种情况, 有2种情况。 时有五种情况，如图： 其实这里已经可以大概猜到是卡特兰数了，但是这里我们做一些更严谨的推导，网上的推导要 展开全文
去ta的博客 赞 (5) 回复(2) 收起
头像 Emcikem
发表于 2020-05-11 10:22:25
知识点总方案数是其中表示每次选择2个，除以表示这n次选择没有先后 而可行数是圆内连弦的个数，是个卡特兰数，不会的可以去上面的博客学习一下卡特兰数以及在圆内连弦的解法 化简总方案数 卡特兰数为 那么答案就是,求(n + 1)! % mod在mod下的逆元乘以 % mod即可 #include < 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 свобода
发表于 2020-05-10 18:41:47
答案是2^n / (n + 1)!。概率可以通过合法方案数/总方案数来计算。合法方案数f(n)=Σf(i) * f(n-i-1), 即为卡特兰数，故f(n)=C(2n, n) / (n + 1)。总方案数为C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”