题意简述

有$n$种能量圈，第$i$种能量是$a_i$。开始你没有能量圈。对于每一天，你有$p$的概率失去一个能量最小的能量圈，有$1-p$的概率可以等概率得到一个能量不大于你现有最小能量圈的能量圈。如果你现在没有能量圈，则不存在概率失去能量圈。

求第一次能量总和超过$T$的期望天数。

$1 \le n \le 30, 1 \le T \le 50, 0.1 \le p \le 0.9$

算法讨论

考虑如果我们知道如何表示一个状态，则不妨设其为$x$。

设$E_x$为$x$达到终态的期望步数。有

$$E_x = (1 - p) \frac{1} {|next(x)|} \sum_{v \in next(x)} {E_v} + p E_{lst(x)} + 1$$

特殊地，对于初始状态有

$$E_{init} = \frac{1} {|next(x)|} \sum_{v \in next(init)} {E_v} + 1$$

高斯消元显然可以解决，但是复杂度过高。我们考虑深入挖掘问题的性质。

仔细观察式子，我们发现，对于一个状态$x$，至多有一个状态$lst(x)$是它的前驱，且存在状态$init$没有前驱。这是一棵树！一个状态的期望仅和它的儿子和父亲有关。

于是我们如果从叶子节点推起，就可以将一个结点的期望化简成$E_x = a E_{lst(x)} + b$的形式。一直推到根结点就得到了答案。

所有只有如何表示状态的问题啦。

考虑到naive的状态表示，就是把每一次得到的能量圈记录下来。我们发现这样其实是可行的，因为有效的状态中能量圈的能量之和必定不超过$T$，而$50$的正整数拆分数约为$200000$，是可承受的。

时间复杂度$O(S(T))$。