这是一道传统的期望题，可是有一些套路值得我去掌握。
我们用$s$来表示一种状态，就是当前拥有的能量圈，是一个正整数拆分的形式。
用$f_{s}$表示如果遇到果冻鱼后丢掉了最小的能量圈后的状态，对于每一个$s$，$f_{s}$是唯一的。
用$v_{s}$表示随机得到了能量圈后的状态，假设目前还有$mi$种能量圈可选，那就有$mi$种转移。
由于$f_{s}$的能量圈个数一定小于$s$的能量圈个数，所以这是一个树形结构。
可以简单写出$s$的期望的方程式：
$E_{s} = 1 + p * E_{f_{s}} + (1 - p) * \frac{1}{mi} * \sum E_{v_{s}}$。
这里我们发现，当$s$的和大于阈值的时候，$E_{s} = 0$，也就是叶子的贡献和其父亲是没有关系的。
这里有一个套路，就是由于它是一个树，每一个$E_{s}$都可以表示成$k_{s} * E_{f_{s}} + b_{s}$的形式。
于是把上式中的$E_{v_{s}}$展开成$k_{v_{s}} * E_{s} + b_{v_{s}}$。
我们设$g = (1 - p) * \frac{1}{mi}, nk = \sum k_{v_{s}}, nb = \sum b_{v_{s}}$，移项可得：
$(1 - g * nk) * E_{s} = 1 + p * E_{f_{s}} + g * nb$
$E_{s} = \frac{p}{1 - g * nk} E_{f_{s}} + \frac{1 + g * nb}{1 - g * nk}$
所以得到$k_{s} = \frac{p}{1 - g * nk}, b_{s} = \frac{1 + g * nb}{1 - g * nk}$。
叶子的$k,b$都是$0$，于是我们只要从叶子向上推就可以了，能算出每个点的$k,b$，因为它只和儿子有关，而根是没有父亲的，答案就是根节点的$b$。
由于阈值不大，正整数拆分的形式不会太多，复杂度是合理的。
$\bigodot$技巧&套路：
- 树上高斯消元的特殊性质
#include <cstdio>
#include <algorithm> using namespace std; int n, t, a[];
double p; struct No { double k, b; }; No Dfs(int s, int mi) {
No re = (No){ , };
if (s > t) return re;
double nk = , nb = ;
double np = s? p : , g = ( - np) / mi;
for (int i = ; i < mi; ++i) {
No so = Dfs(s + a[i], i + );
nk += so.k, nb += so.b;
}
re.k = np / ( - g * nk);
re.b = ( + g * nb) / ( - g * nk);
return re;
} int main() {
while (scanf("%lf%d%d", &p, &t, &n) == ) {
for (int i = ; i < n; ++i)
scanf("%d", &a[i]);
sort(a, a + n);
printf("%.3f\n", Dfs(, n).b);
}
return ;
}