[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP，倒着考虑正常一点（因为在 $n-1$ 处结束，步数为 $0$ ），所以我们倒着DP。定义 $f(i)$ 表示 $i$ 走到 ...
[期望的线性性+概率DP]TopCoder【RockPaperScissors】题解
题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $n$ 次剪刀石头布，赢了得 $3$...
[期望的线性性+概率DP]HHHOJ164【排列统计】题解
解题报告其实不用管期望……只要算出总贡献然后最后除以 $(n^2)^k$ 就行了（Manchery：期望就是层壳），不过也可以利用期望的线性性把期望转成概率。算贡献的时候如果真的按照题目中给的...
[期望DP]BZOJ4832(Lydsy1704月赛)【抵制克苏恩】题解
题目概述刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。奴隶主被攻击之后没死并且现在的奴隶...
[期望DP+高斯消元+复杂度分析]Codeforces963E【Circles of Waiting】题解
题目概述从原点出发，每次往上下左右走都有一定的概率，问第一次走到离原点距离超过 $R$ 的点的期望步数。解题报告很显然可以期望DP，令距离超过 $R$ 但最接近原点的一圈的 $f_{x,y}=0...
