首页 > 序列取反问题
开通博客写题解
头像 GhostLX
发表于 2021-08-27 21:08:04
题目陈述 大意：给定一排牛牛，一开始都是不快乐的牛牛，每次等概率选择一个当前不快乐的牛牛，将[i,a[i])[i,a[i])[i,a[i])中的牛牛都变为快乐，最后所有的牛牛都变为快乐的在modmodmod mmm意义下，的期望步数是多少？ 前置知识 这题是一个ACM竞赛中很经典的树上期望问题，在 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 George_Plover
发表于 2021-09-05 22:42:31
题意整理： 基本题意 ​ 有一个长度为 nnn 的序列 {ai}(i=0,1,2,<mtext> </mtext>...<mtext> </mtext>,n−1)\{a_i\}(i=0,1,2,\ ...\ ,n-1){ai​}( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bibibibi
发表于 2021-09-12 19:24:15
题目陈述 简介：给定一个数组，每次选择一个区间 染色，保证区间不存在相交，只有相离和包含两种关系，问将整个数组染色的期望，答案对取模。 前置知识 逆元 求某个数在某个模数下的逆元，即求，使得，因此，取模意义下的除法等价于乘该数的逆元 一般在题目当中是一个素数，常见的算法是费马小定理，费马小定理内容 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 abcdhhhh
发表于 2021-09-06 23:42:38
题意 给定数组 满足 ，特别地， 。 或 。 起初这些数均未被标记。每次可以在未标记的数中任选一个 ，并标记下标在 中的所有数。求将所有数均标记所需的期望次数。 解法1：状压DP（MLE+TLE） 我们用一个 位二进制数 表示 中元素被标记的状态（第 位的 表示 被标记， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-09-02 23:22:08
题意整理 给定一个序列，序列中每个下标对应一个值，选定一个下标i，则从i到的区间所有数都做一个标记。 最后的目标是将所有的数都打上标记，问所有可能的方案中期望步数是多少。 方法一（排列+费马小定理+快幂法） 1.解题思路 对于任意均满足条件：若，则这两个条件一定满足其中1个。所以，如果，要么， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 简单666
发表于 2021-09-12 13:57:41
题意： 给你一个长度为的序列，第个数字代表了一段连续的区间， 其中这些区间满足要么完全覆盖，要么不相交， 现在每次等概率地随机选择一个点，并且将区间全部打上标记， 问期望多少次能将整个序列都打上标记（答案对998244353取模）？ 解法一（问题转化+暴力求解） 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”