标签: 期望概率

「CF1349D」 Slime and Biscuits

Slime and his nn friends are at a party. Slime has designed a game for his friends to play.
At the beginning of the game, the ii-th player has aia_i
biscuits. At each second, Slime will choose a biscuit randomly uniformly among all a1+a2++ana_1 + a_2 + \ldots + a_n biscuits, and the owner of this biscuit will give it to a random uniform player among n1n-1 players except himself. The game stops when one person will have all the biscuits.

As the host of the party, Slime wants to know the expected value of the time that the game will last, to hold the next activity on time.

For convenience, as the answer can be represented as a rational number pq\frac{p}{q}
​for coprime pp and qq , you need to find the value of (pq1)mod998244353(p \cdot q^{-1})\mod 998\,244\,353. You can prove that qmod9982443530q\mod 998\,244\,353 \neq 0

「HNOI2015」亚瑟王

小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。

作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。
(即 ii 等于 nn),则结束这一轮;否则,考虑下一张卡牌。

请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

「P3412」 仓鼠找sugar II

小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a,是任意的)他的基友卧室(b,还是任意的)。(注意,a有可能等于b。)然而小仓鼠学OI学傻了,不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时,等概率到这个点的母亲或者所有孩子节点(例如这个节点有一个母亲节点和两个子节点,那么下一步走到这3个节点的概率都是1/3)。一但走到了他基友的卧室,就会停下。

「NOI2005」聪聪与可可

在一个魔法森林里,住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽 然灰姑娘非常喜欢她们俩,但是,聪聪终究是一只猫,而可可终究是一只老鼠, 同样不变的是,聪聪成天想着要吃掉可可。

一天,聪聪意外得到了一台非常有用的机器,据说是叫 GPS,对可可能准确 的定位。有了这台机器,聪聪要吃可可就易如反掌了。于是,聪聪准备马上出发, 去找可可。而可怜的可可还不知道大难即将临头,仍在森林里无忧无虑的玩耍。 小兔子乖乖听到这件事,马上向灰姑娘报告。灰姑娘决定尽快阻止聪聪,拯救可 可,可她不知道还有没有足够的时间。

[六省联考2017] 分手是祝愿

B 君在玩一个游戏,这个游戏由 n 个灯和 n 个开关组成,给定这 n 个灯的初始状态,下标为从 1 到 nn 的正整数。

每个灯有两个状态亮和灭,我们用 1 来表示这个灯是亮的,用 0 表示这个灯是灭的,游戏的目标是使所有灯都灭掉。

「HNOI2013」游走

给定一个 n 个点 m 条边的无向连通图,顶点从 1 编号到 n,边从 1 编号到 m。

小 Z 在该图上进行随机游走,初始时小 Z 在 1 号顶点,每一步小 Z 以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 n 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 m 条边进行编号,使得小 Z 获得的总分的期望值最小。

「HDU 5985」Lucky Coins

Bob has collected a lot of coins in different kinds. He wants to know which kind of coins is lucky. He finds out a lucky kind of coins by the following way. He tosses all the coins simultaneously, and then removes the coins that come up tails. He then tosses all the remaining coins and removes the coins that come up tails. He repeats the previous step until there is one kind of coins remaining or there are no coins remaining. If there is one kind of coins remaining, then this kind of coins is lucky. Given the number of coins and the probability that the coins come up heads after tossing for each kind, your task is to calculate the probability for each kind of coins that will be lucky.

「SCOI2008」奖励关

你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。

宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。也就是说,即使前k-1 次系统都抛出宝物1(这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。

「LightOJ 1027」A Dangerous Maze

You are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a door is equal for all doors.

If you choose the ith door, it can either take you back to the same position where you begun in xi minutes, or can take you out of the maze after xi minutes. If you come back to the same position, you can't remember anything. So, every time you come to the beginning position, you have no past experience.

Now you want to find the expected time to get out of the maze.