首页 > 其他分享 >CF1854C Solution

CF1854C Solution

时间:2023-10-15 14:35:38浏览次数:39  
标签:取模 题意 Solution CF1854C 每一秒 sim

题目链接

题意

给定大小为 \(n\) 的正整数集合 \(S\),\(S\) 中的每个数在 \(1\sim m\) 之间。

每一秒进行如下操作:

  1. 从 \(S\) 中等概率随机选择一个数 \(x\)。
  2. 将 \(x\) 从 \(S\) 中删去。
  3. 若 \(x + 1\leq m\) 且 \(x + 1\notin S\),则将 \(x + 1\) 加入 \(S\)。

求 \(S\) 变成空集的期望时间,对 \(10 ^ 9 + 7\) 取模。

Solution

标签:取模,题意,Solution,CF1854C,每一秒,sim
From: https://www.cnblogs.com/nullptr-qwq/p/17765588.html

相关文章

  • Argument for '--moduleResolution' option must be: 'node', Unknown compiler opt
    node_modules/@vue/tsconfig/tsconfig.json(12,25):errorTS6046:Argumentfor'--moduleResolution'optionmustbe:'node','classic','node16','nodenext'.node_modules/@vue/tsconfig/tsconfig.json(33,5):erro......
  • IDM:Implicit Diffusion Models for Continuous Super-Resolution超分辨率
    摘要当今超分辨领域的模型普遍存在过度平滑(难以保持放大后图像的锐利和纹理,导致高频信息丢失和视觉上变得平滑)和伪影(生成的高分辨率图像中可能出现的不希望出现的失真或瑕疵,包括模糊、马赛克效应或者不自然纹理等)的现象,作者据此提出了IDM模型,IDM模型是在一个统一的端到端框架中集......
  • Perkins 1106D Generation CID 0003 FMI 05 Trouble Code Solution
     ThisillustrationgivethesolutionforPerkins1106Delectricpowergeneration(EPG)CID0003FMI05troublecode.RelatedContents:PerkinsESTCompactAdapterPerkinsEST2023A&2022A&2019ASoftwareFreeDownloadPerkins1106DElectricPower......
  • Solution of 牛客集训提高组第三场2023B 摆渡车
    \(\text{Description}\)有\(n\)个乘客要依次经过检票口等待摆渡车,其中第\(i\)个人的重量为\(a_i\),摆渡车载重为\(M\)。当乘客\(i\)通过检票口时摆渡车来了则他能优先登上摆渡车。剩下的\(1\simi-1\)则尽可能多上人到摆渡车上。对于每个\(i\)求如果在......
  • Solution-AGC018F
    对于全幺模阵刻画限制的一般方法。先写出限制:\(\sum_{v\in\text{sub}(u)}a_v=\{1,-1\}\)。嘛虽然你可以通过奇偶性(大概)把限制改成\(|\sum_{v\insub(u)}a_u|\leq1\),但是我们还是别这么做吧。考虑转化一下限制。设\(a_u\)表示\(u\)在第一棵树上的子树和,\(b_u\)表示\(u......
  • Solution -「ARC 106E」Medals
    Desc.  Link.  你有\(n\)个朋友,他们会来你家玩,第\(i\)个人\(1...A_i\)天来玩,然后\(A_i+1...2A_i\)天不来,然后\(2A_i+1...3A_i\)又会来,以此类推;  每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。  你要给每个人都颁\(K\)个奖,问至少需要多少......
  • The solution of P3012
    problem&blog很明显是个DP。于是我们定义\(dp_{i,j,k}\)为末尾的字符的ASCII码为\(i\),有\(j\)个大写字母,\(k\)个小写字母。然后在枚举能接在\(i\)之后所有字母即可。然后考虑\(dp_{i,j,k}\)给后面的DP值得贡献。所以就有:\[dp_{\text{能接在i后面的字母},j......
  • The solution of ABC144F
    都不知道什么时候做的题了problem&blog一开始很容易想到枚举断边然后DP算代价。于是很容易想到DP状态定义:设\(dp_u\)为从\(u\)出发到\(n\)的期望步数。那么显然有\(dp_u=\sum^{v_n}_{v_1}\dfrac{dp_{v_{i}}}{d_u}\),其中\(d_u\)为\(u\)的出度。如果选择......
  • Solution -「JOISC 2020」建筑装饰 4
      朴素的DP形式是定义\(f_{i,j,A/B}\)表示前\(i\)个元素选择了\(j\)个\(A\)的可达性.\(\mathcalO(n^2)\).交换状态与值域,定义\(f_{i,A/B,A/B}\)表示前\(i\)个元素中的最后一个元素(即\(i\))选择了\(A/B\),在最大化\(A/B\)的数量的目标下求得的\(......
  • Solution of 洛谷-P1896
    并不会有更好的阅读体验\(\text{Sol}\)我们先看一眼数据范围:\(1\leN\le9\)没关系,DFS会出手。好吧,正经的说,如果暴搜的话复杂度会涨到\(\textO(2^{n^2})\),\(\textT\)到飞起。此时我们发现有个东西叫状压\(\text{DP}\),也是解决小范围数据的问题。老套路,枚举每一行,......