题意：(感觉题面写的题意是错的?)有\(n\)种能量不同的圈，设当前拥有的圈的集合为\(S\),则：

1，每天有\(p\)概率失去一个能量最小的圈。特别的，如果\(S = \varnothing\),那么这个概率为0.

2，否则将得到一个满足\(能量 \le S_{min}\)的圈。

求\(S\)内的能量和大于\(T\)的期望天数。

题解：出于期望要倒推的考虑，我们设\(f[i]\)表示从状态\(i\)到合法状态的期望。

一个能量和大于\(T\)的状态为合法状态，显然有\(f[合法状态] = 0\)，现在我们要求的是\(f[\varnothing].\).

令\(last(i)\)表示状态\(i\)通过删去一个圈可以到达的状态。\(next(i)\)表示状态\(i\)通过获得一个圈可以到达的状态。我们可以列出如下等式：

\[f[i] = 1 + p \cdot f[last(i)] + (1 - p) \frac{1}{|next(i)|}\sum{f[next(i)]}\]

高斯消元？但状态好像太多了，，，权值和为\(50\)的不同集合个数大概在\(1e5\)的级别，\(n^{3}\)不可能过。所以我们考虑优化。

因为对于一个集合\(S\),去掉一个圈可以到达的状态是唯一确定的，因此\(last(s)\)只有一个，但\(next(s)\)有多个。

所以如果我们将\(last(s)\)视作\(s\)的父亲，\(next(s)\)视作\(s\)的儿子，那么我们可以发现，以状态之间的关系为边，可以构建出一棵树。

如果我们可以把\(f[i]\)表示为\(k \cdot f[fa(i)] + b\)的形式，那么对于任意一个点，我们将它子树所表示出的所有式子带入消值，可以使得当前点的式子中最多只有\(f[i]\)和$f[fa(i)]$2个状态。

我们考虑用归纳法来证明这是可行的：

1，对于叶子节点(合法状态)，因为它本身就没有儿子，因此一开始就只有自己和父亲2个状态，显然可以表示成所需状态。

2，对于非叶节点，考虑证明当儿子满足条件时，这个节点一定满足条件。

\[f[i] = 1 + p \cdot f[last(i)] + (1 - p) \frac{1}{|next(i)|}\sum{f[next(i)]}\]

其中\((1 - p) \frac{1}{|next(i)|}\)是一个定值，我们设它为\(G\).那么：

\[f[i] = 1 + p \cdot f[last(i)] + G\sum{f[next(i)]}\]

变成高斯消元的形式：

\[f[i] - p \cdot f[last(i)] - G\sum{f[next(i)]} = 1\]

其中，因为\(i\)的儿子，也就是\(next(i)\)会被转化为\(k \cdot f[i] + b\)的性质，因此当我们把\(next(i)\)全都带入进来后,剩下的式子应该是类似这样的.其中\(f[i]\)的系数和常数项被改变，于是得到：

\[k_{1}f[i] = k_{2} + p \cdot f[last(i)]\]

稍微化简一下可以得到：

\[f[i] = \frac{p}{k_{1}} f[last(i)] + \frac{k_{2}}{k_{1}}\]

设\(t_{1} = \frac{p}{k_{1}}, t_{2} = \frac{k_{2}}{k_{1}}\),则：

\[f[i] = t_{1}f[last(i)] + t_{2}\]

考虑一点细节上的东西：

\[f[i] - p \cdot f[last(i)] - G\sum{f[next(i)]} = 1\]

考虑将\(f[next(i)] = af[i] + b\)带入原式会产生什么样的影响。

\[-G(af[i] + b) = -Gaf[i] - Gb\]

设\(f[i]\)的系数为\(k_{1}\),常数项为\(k_{2}\).

\[f[i] - p \cdot f[last(i)] -Gaf[i] - Gb = 1\]

显然我们只需要将\(k_{1} -= Ga, k_{2} += Gb\)即可

#include
    
     using namespace std;#define R register int#define AC 55#define ld doubleint n, T;int v[AC];ld p, t1[AC][AC], t2[AC][AC];inline int read(){    int x = 0;char c = getchar();    while(c > '9' || c < '0') c = getchar();    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x;}void pre(){    T = read(), n = read();    for(R i = 1; i <= n; i ++) v[i] = read();    sort(v + 1, v + n + 1);    memset(t1, 0, sizeof(t1));    memset(t2, 0, sizeof(t2));}void dfs(int x, int lim){    if(x > T) return;    if(t1[x][lim] > 0 || t2[x][lim] > 0) return ;//记忆化？但这样的话就需要初始化了    //printf("%d %d\n", x, lim);    ld p1 = x ? p : 0;//在计算之前要修改概率    ld k1 = 1, k2 = 1, G = (1.0 - p1) * (1.0 / lim);    //printf("???%lf\n", G);    for(R i = 1; i <= lim; i ++)    {        int now = x + v[i];        if(now > T) continue;//如果不加这个判断的话，数组就要开100，，，因为now可以到100.。。        dfs(now, i);        k1 -= G * t1[now][i], k2 += G * t2[now][i];    }       t1[x][lim] = p / k1, t2[x][lim] = k2 / k1;}void work(){    while(scanf("%lf", &p) != EOF)    {        pre(), dfs(0, n);        printf("%.3lf\n", t2[0][n]);    }}int main(){//  freopen("in.in", "r", stdin);    work();//  fclose(stdin);    return 0;}