【luogu p4548】歌唱王国（期望）（生成函数 / 思维）（kmp）-爱代码爱编程
歌唱王国 题目链接：luogu P4548 题目大意 多次询问，每次给你一个字符串，然后有 n 种字符，猴子随机打字。 每个字符打出来的概率相同，然后打出一个串使得给出串是它的子串就停止，问你停止的时候打出来的字符串的
【ybt2023寒假day8 b】期望题（期望dp）-爱代码爱编程
期望题 题目链接：YBT2023寒假Day8 B 题目大意 给你一个 n 个节点的数，每个点有黑色或者白色。 你一开始在 1 号点，一直进行下面的操作： 如果点第一次到或者是黑色就把计数器加一，然后如果当前点度数为 1
【ybt2023寒假day3 a】千与千寻（期望dp）（高斯消元）-爱代码爱编程
千与千寻 题目链接：YBT2023寒假Day3 A 题目大意 一个 n*m 的平面，你要从 (0,0) 走到 (x,y)，你等概率的向上或向右走，然后当你走到 (n-1,i) 再往右走，就是 (0,i)，走到 (i,m
【luogu agc032f】one third（数学）（期望）_ssl_tjh的博客-爱代码爱编程
One Third 题目链接：luogu AGC032F 题目大意 有一个环，你每次会随机选一个半径切一刀，然后最后形成若干块，要你选一段连续的块，使得它们的面积和最接近 1/3，问你这个距离的最小期望。 思路 有
【luogu p6130】随机红包（数学）（期望）_ssl_tjh的博客-爱代码爱编程
随机红包 题目链接：luogu P6130 题目大意 把一个数 1 分成 n 份，求第 k 小的期望大小，多次询问。 思路 首先考虑最小的期望大小，那假设最小的是
【gym102979e】expected distance（期望dp）_ssl_tjh的博客-爱代码爱编程
Expected Distance 题目链接：gym102979E 题目大意 有一棵树，第 i 个点的父亲再 1~i-1 中根据每个数的 a 值乘正比概率出现，然后边的长度是两端的点的 b 值的和。 然后多组询问每次问
【luogu CF1153F】Serval and Bonus Problem（期望）（DP）-爱代码爱编程
Serval and Bonus Problem 题目链接：luogu CF1153F 题目大意 长度为 l 的线段，有 n 个区间端点随机分布，然后问你期望有多少长度被至少 k 个区间覆盖。 思路 首先这种随机分布的期望题考虑也把随机的时间弄成一个平均分布。 在这里就是我们可以理解为这
【多校】H. Playf and Tree-爱代码爱编程
H. Playf and Tree 一道比较基础的期望加树的遍历。对于操作次数的期望便是所有的点被直接操作的概率相加。 对于一个节点 ，它是确定的一定要被删除的，但是它删除的方式有两种，即要么是删除了它的一个祖先节点，要么是直接删除它自己 。直接删除的概率是它的深度的倒数。那么考虑所有点，它们被直接删除的概率都是其深度的倒数 ，那么在每个点上需要花费一
【YBT2022寒假Day7 C】【luogu CF603E】以线覆圆 / Arcs on a Circle（期望）（DP）-爱代码爱编程
以线覆圆 / Arcs on a Circle 题目链接：YBT2022寒假Day7 C / luogu AT3860 题目大意 给你一个周长为 n 的圆和一些长度的线段。 然后每条线段会随机出现在圆中，然后问你这些线段把整个圆覆盖的期望。 思路 我们首先考虑如果线段端点只能是整数，那我们不难有个方法：断环为链来 DP。（然后为了保证不重，我们保
【YBT2022寒假Day2 A】期望旅行（Dij）（期望DP）-爱代码爱编程
期望旅行 题目链接：YBT2022寒假Day2 A 题目大意 给你一个无向图，然后每个边有出现的概率，自环必定出现。 然后问你在最优策略下你从 1 1 1 点走到
【ybtoj高效进阶 21269】乐园之旅（期望DP）-爱代码爱编程
乐园之旅 题目链接：ybtoj高效进阶 21269 题目大意 给你一个无重边无自环的无向图，每个点有分数和需要时间，然后边也需要时间。 小明小红会等概率选择一个点作为出发点，先获得出发点的分数（同时也耗了时间），然后每次等概率的选择可以一步走到而 且有关的点进行得分。 要你分别计算小明和小红的得分期望。 思路 首先不难看出两个人的计算是分开的。
【ybt高效进阶6-6-1】【luogu P1297】单选错位（期望）-爱代码爱编程
单选错位 题目链接：ybt高效进阶6-6-1 / luogu P1297 题目大意 有 n 个单选题，每道题有一定的选项，然后每道题的答案是在每个选项中等概率随机一个。 然后你问你如果你的答案都是对的，但是你都填到了下一题的位置（如果是最后一题就填到第一题），你能对的题的期望个数。 思路 首先不难想到要能对就是要相邻两个选项是选的一样。 那我们
随机游走 / T1（期望）（树形DP）-爱代码爱编程
随机游走 / T1 题目大意 给你一个树，问你对于每个点对 (i,j)，i 走到 j 的期望步数的最大值。 行走的方式是在可以一步到达的点中等概率的选择一个走过去。 思路 首先我们观察样例，发现如果一个点是叶子节点（或者说度数是 1
【ybtoj高效进阶6-6-3】 路径长度/【luogu P4316】绿豆蛙的归宿-爱代码爱编程
路径长度 【ybtoj高效进阶6-6-3】】/【luogu P4316】 绿豆蛙的归宿 题面： 因为题目不好抽取大意所以顺便放上来了。 给出一张n个点 m 条边的有向无环图，起点为1 ，终点为n ，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。 绿豆蛙从起点1出发，走向终点n。到达每一个顶点时，如果该节点有 k 条出
【ybtoj高效进阶6-6-2】 期望分数/WJMZBMR打osu! / Easy 【luogu P1365】-爱代码爱编程
期望分数【ybtoj高效进阶6-6-2】 WJMZBMR打osu! / Easy 【luogu P1365】 题目描述： 给定一个长度为n的由 o,x,? 组成的字符串。计算分数的规则如下：连续 a 个 o 可以得到 a
【ybtoj高效进阶6-6-1】【luogu P1297】单选错位【期望】-爱代码爱编程
单选错位【ybtoj高效进阶6-6-1】【luogu P1297】 思路：【期望模板题】 一道非常基础的期望题，竟然不是期望DP 我们设答对第i道题的概率为 p [ i
【jzoj 3661】【luogu P4284】Charger / 概率充电器（期望DP）（换根DP）-爱代码爱编程
Charger / 概率充电器 题目链接：jzoj 3661 / luogu P4284 题目大意 有一些点，一个点有亮不亮两种可能。 一个点本身有一定的概率会亮，然后点之间有边，把点连接构成了一棵树。 然后每条边有一定概率，使得如果两边有一个点亮了，另一边也会亮。 问你亮的点的期望个数。 思路 你可以求出每个点亮的概率，然后加起来就是期望。 你
【机房练习赛 5.5】 atm 自动取款机-爱代码爱编程
题面 题目描述 小沈阳在小品里说过：“人生最痛苦的事情是人死了，钱还没花了”。 于是小宋（80 岁）决定要将所有的储蓄从ATM 机中取出花光。小宋忘记了她有多少存款 （银行卡密码她是记得的2333），这个奇怪的ATM 不支持查询存款余额功能。小宋知道她 存款的唯一信息是存款上限是 K
【ybt金牌导航1-1-8】【luogu P3750】关灯游戏 / 分手是祝愿-爱代码爱编程
关灯游戏 / 分手是祝愿 题目链接：ybt金牌导航1-1-8 / luogu P3750 题目大意 有一些从一到 n 编号灯泡与按钮。按下某个编号的按钮，它所有约数的灯都会由开变关，由关变开。 每次等概率随机操作一个开关，直到所有灯都灭掉。 但如果某个时候可以按不超过 k 个开关使所有灯灭掉，那么他会直接选操作次数最小的方法操作。 问你操作次数
【ybt金牌导航1-1-7】【luogu P6089】选书问题 / 非诚勿扰-爱代码爱编程
选书问题 / 非诚勿扰 题目链接：ybt金牌导航1-1-7 / luogu P6089 题目大意 就是有两种点，第一种的点会与一些第二种点连接，然后对于每一个连着的第二种点，这个第一种的点会有 p 的概率选择这个点，否则就跳到下一个和它连着的点。然后如果一直到最后一个都不选，就跳到第一个继续。 问你期望逆序对的概率。 思路 我们看第一种点连着