陌研

题解

/ 注册

全部文章 / 题解（共20篇）

题解 | #Messages#

【Messages】定义X=∑inxiX=\sum_{i}^nx_iX=∑inxi为读到需要的信息的学生的数量，其中xix_ixi为第iii个学生是否读到自己需要的信息，如果读到就为111，否则为000。根据期望的可加性可知: E(X)=E(x1)+E(x2)+..+E(xn)\mathb...

概率数学 C++

2022-04-14

2 424

题解 | #Checkpoints#

【Checkpoints】定义E(i)\mathbb{E}(i)E(i)为从第iii关开始到通关，所需要通过的关卡的期望。假设从第 lll 关开始到第 rrr 关只有第 lll 关有存档点，那么： E(l)=12(E(l)+E(l+1))+1E(l+1)=12(E(l)+E(l+2))+1⋯E(...

概率数学 C++

2022-04-14

3 452

题解 | #Fork in the Road#

【Fork in the Road】定义dp(i)dp(i)dp(i)为从房间iii到结束的期望。先不考虑删边的情况，状态转移： {dp(u)=∑u→v1Graph[u].size⋅(dp(v)+1),u≠ndp(u)=0,u=n\begin{cases} dp(u)=\sum_{u\right...

概率数学 C++

2022-04-14

2 358

题解 | #New Year and Arbitrary Arrangement#

【New Year and Arbitrary Arrangement】定义dp(i,j)dp(i,j)dp(i,j)为子序列"ab"的个数为iii且存在jjj个"a"时的期望。状态转移为： dp(i,j)=PaPa+Pbdp(i,j+1)+PbPa+Pbdp(i+j,j)dp(i,j)=\fr...

概率数学 C++

2022-04-14

6 391

题解 | #Little Pony and Expected Maximum#

【Little Pony and Expected Maximum】定义P(Y=y)P(Y=y)P(Y=y)为投nnn次，得到最大点数为yyy的概率，但是这个值直接计算比较难。可以先定义P(Y≤y)P(Y\le y)P(Y≤y)为最大点数小于yyy的概率，则P(Y=y)=P(Y≤y)−P(Y≤y...

概率数学 C++

2022-04-14

1 384

题解 | #increment of coins#

【increment of coins】定义dp(i,j,k)dp(i,j,k)dp(i,j,k)为背包中分别有iii枚金币，jjj枚银币，kkk枚铜币时，操作次数的期望。末态为已经存在某一种硬币有100枚，即 dp(100,i,j)=dp(i,100,j)=dp(i,j,100)=0;dp(1...

数学概率 C++

2022-04-14

4 465

题解 | #擅长解密的小红同学#

【擅长解密的小红同学】设密码有NNN中可能，那么每次猜中的概率为: P=1NP=\frac{1}{N}P=N1 那么，猜了kkk次猜中的概率为: P(X=k)=(1−P)k−1PP(X=k)=(1-P)^{k-1}PP(X=k)=(1−P)k−1P，即前k−1k-1k−1次都没猜中，而第kkk次...

概率数学 C++

2022-04-14

2 386

题解 | #GCD Table#

【GCD Table】若选中的起始位置为(i,j)(i,j)(i,j)，则： <mstyle displaystyle="false" scriptlevel="0">{<mstyle displaystyle="false&q...

数学 excrt

2021-10-29

1 554

题解 | #Power Tower#

【Power Tower】 m→φ(m)→φ(φ(m))→...→1m\rightarrow \varphi(m) \rightarrow \varphi(\varphi(m)) \rightarrow...\rightarrow1m→φ(m)→φ(φ(m))→...→1 ，这个步骤最多会进行log...

欧拉降幂欧拉函数数学

2021-10-29

1 460

题解 | #Notepad#

【Notepad】欧拉降幂裸题。所有nnn位bbb进制的数有bnb^nbn个，含前导000的数有bn−1b^{n-1}bn−1个，总共需要记录的数有bn−bn−1=(b−1)bn−1b^n-b^{n-1}=(b-1)b^{n-1}bn−bn−1=(b−1)bn−1个，直接对ccc取模。当...

欧拉降幂数学欧拉函数

2021-10-29

3 416