CF441E Valera and Number - Solution

先把原题的 $p$ 除 $100$。

简单来说，$x$ 开始，$p$ 概率乘 $2$，$1 - p$ 概率加 $1$，求期望末尾 $0$ 个数。

最朴素想法是设 $f_{i,\,v}$ 代表 $i$ 次操作后 $x$ 变为 $v$ 的概率，当然这个状态数超级大，没啥讨论的必要。

$k$ 对比之下显得很小，接下来有几条路可以走。

不过我们的 $x$ 毕竟是一个任意的数，它是完全有可能加一些 $1$ 就产生超过 $8$ 位的进位的。

那我们把 $8$ 位以上连续 $1$ 的个数也加入状态，毕竟显然超过 $8$ 位的进位至多只有一次。

不过这样就要把两个过程拆开来，毕竟这种情况我们默认产生了进位，并且后面没有 $+1$ 把进位产生的这坨 $0$ 顶掉。所以如果超八位进位后还有加 $1$，那么进位产生的这坨 $0$ 对最终末尾 $0$ 的个数当然产生不了影响，于是要设另一个 dp 来转移这种情况。

设 $f_{i,\,j,\,k}$ 代表前 $i$ 次操作使得八位以上末尾连续 $1$ 的个数是 $j$，且末尾八位是 $k$ 的概率。

$g_{i,\,j}$ 代表前 $i$ 次操作，末尾有 $j$ 个零的方案数，强制令 $j > 8$。

写起来会比较复杂，但总之我们容易获得一个 $\Theta(k^3)$ 的做法。

不难发现我们是越靠后的操作产生的影响越大。比如我们在末尾进行了几次乘 $2$，那么继续往前的加 $1$ 肯定不会对最低位产生影响。

假设我们末尾进行了 $t$ 次乘 $2$，在这坨乘 $2$ 之前我们对 $x$ 产生了 $+w$ 的影响

首先如果 $w$ 是偶数，那么可以看成 $t + 1$ 次乘 $2$ 和前面 $+\frac{w}{2}$ 的的影响。

如果 $w$ 是奇数，显然我们的末尾 $0$ 个数直接就是 $t$ 了。

$f_{i,\,j,\,w}$ 代表进行了末尾 $i$ 次操作，并且结尾有 $j$ 个乘 $2$，在这 $j$ 个乘 $2$ 之前有 $+w$ 的影响。

转移上面直接得出来了，讨论 $w$ 的奇偶性即可。

至于 $w$ 的范围，只有加 $1$ 是能扩展 $w$ 的范围的，至多有 $k$ 次加 $1$。

复杂度 $\Theta(k^3)$。

上面这个东西其实可以做得更好，我们为什么要把末尾乘 $2$ 的数量 $j$ 纳入状态，因为我们要在最后乘上一个 $p$ 的 $j$ 次方得到这个状态的概率，但是我们知道期望具有线性性，于是可以把 $j$ 这一维直接去了，直接乘 $p$ 贡献给答案。

大概是个这样的东西：

if (j mod 2 == 0) f[i + 1][j / 2] += f[i][j] * p, ans += f[i][j] * p;
f[i + 1][j + 1] += f[i][j] * (1 - p);

时间复杂度 $\Theta(k^2)$。