Description：

有 $N$ 种能量圈，每天有 $1-p$ 的概率等概率的得到一个能量圈， $P$ 的概率失去一个能量圈，问期望多少天后能量圈的能量总和达到 $T$ 。

$1\leqslant N,T\leqslant 50$

Solution：

因为 $T$ 最大只有 $50$ ，因此状态数实际上是非常少的，首先我们可以暴力 $DP$ ： $$ f[i]=1+p\times f[last[i]]+(1-p)\times \frac1{|nxt[i]|}\times\sum_jf[nxt[i][j]] $$ 由于每个点只有一个 $last[i]$ ，所以转移形成了一棵树。

然后有一个套路叫做树上消元，也就是上面那个 $DP$ 式子我们可以高斯消元，但是由于是一棵树我们可以用另一些做法来优化复杂度：

考虑把 $f[i]$ 表示成 $f[i]=K_if[last[i]]+B_i$ 的形式，先假装他成立： $$ \begin{align} f[i]&=1+p\times f[last[i]]+(1-p)\times \frac1{|nxt[i]|}\times \sum_jK_{nxt[i][j]}f[i]+(1-p)\times \frac1{|nxt[i]|}\times \sum_jB_{nxt[i][j]}\\ 设&A_i=(1-p)\times \frac1{|nxt[i]|}\\ (1-&A_i\times \sum_jK_{nxt[i][j]})f[i]=1+p\times f[last[i]]+A_i\times \sum_jB_{nxt[i][j]}\\ f[i]&=\frac p{1-A_i\times \sum_jK_{nxt[i][j]}}\times f[last[i]]+\frac{1+A_i\times \sum_jB_{nxt[i][j]}}{1-A_i\times \sum_jK_{nxt[i][j]}}\\ \end{align} $$ 即： $$ K_i=\frac p{1-A_i\times \sum_jK_{nxt[i][j]}},B_i=\frac{1+A_i\times \sum_jB_{nxt[i][j]}}{1-A_i\times \sum_jK_{nxt[i][j]}} $$ 于是直接求一遍就行了，最后根节点的 $B$ 就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,t;

#define MAXN 51

double p;

int a[MAXN];

struct state

{

    double k,b;

};

state dfs(int sum,int minv)

{

    if(sum > t)return (state){0,0};

    double sumk = 0,sumb = 0;

    for(int i = 1;i <= minv;++i)

    {

        state nxt = dfs(sum + a[i],i);

        sumk += nxt.k;sumb += nxt.b;

    }

    double P = sum ? p : 0;

    double A = (1 - P) / minv;

    sumk = 1 - A * sumk;sumb = 1 + A * sumb;

    double k = P / sumk,b = sumb / sumk;

    return (state){k,b};

}

int main()

{

    while(~scanf("%lf%d%d",&p,&t,&n))

    {

        for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

        sort(a + 1,a + 1 + n);

        printf("%.3lf\n",dfs(0,n).b);

    }

    return 0;

}