题目大意

有一个数集 $A$。

维护一个可重集 $S$，若集合不为空，每天有 $p$ 的概率去掉最小值。剩下的 $1-p$ 的概率中，等概率的添加 $A$ 中小于 $S$ 的所有元素的一个元素。

当集合中所有的元素之和大于 $T$ 时进化成强大模式。

求进化的期望天数。

题目解法

我们设 $f(S)$ 为当前集合期望的进化天数。

$$
f(S) = p f(P) + \frac{1-p}{m} \sum_{i=1}^m f(T) + 1
$$

其中 $P$ 表示 $S$ 去掉最小值后的集合，$T$ 表示 $S$ 加上一个元素后的集合，即题目中说的两种操作所对应的集合。

我们可以发现 $T$ 去掉其最小值后为 $S$。

所以这构成了一颗树的形式，其中叶子节点即已经进化了的集合，根节点即空集。

考虑消除后效性，运用数学归纳法，假设对于所有的节点都有 $f(S) = k f(P) + b$。

归纳奠基，对于叶子节点，可令 $k = b = 0$，显然成立。

对于一个非叶子节点：

$$
f(S) = p f(P) + \frac{1-p}{m} \sum_{i=1}^m k_i f(S) + b_i + 1
$$

记：

$$
t = \frac{1-p}{m},\ K = \sum_{i=1}^m k_i,\ B = \sum_{i=1}^m b_i
$$

有：

$$
f(S) = \frac{p}{1 - t K} f(P) + \frac{1 + t B}{1 - t K}
$$

即证。

当 $S$ 为空集的时候 $f(S)$ 就是我们要求的答案，然而此时 $f(P) = 0$ 故只需求 $\varnothing$ 处的 $b$ 即可。

我们递归处理即可。

值得注意的是，我们可以只用集合元素之和与集合元素最小值来描述集合，另当 $S = \varnothing$ 时应令 $t = \frac{1}{m}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
#define P pair<double,double>
#define fir first
#define sec second
double p;
int T,n;
int a[maxn+5];
P Dfs(int sm,int mn){
    if(sm>T) return P(0,0);
    else{
        double k=0,b=0;P tmp;
        for(int i=1;i<=mn;i++){
            tmp=Dfs(sm+a[i],i);
            k+=tmp.fir,b+=tmp.sec;
        } 
        double t;
        if(sm) t=(1-p)/mn;
        else t=1.0/mn;
        return P(p/(1-t*k),(1+t*b)/(1-t*k));
    }
}
signed main(){
    while(scanf("%lf%d%d",&p,&T,&n)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        printf("%.3lf\n",Dfs(0,n).sec);
    }
    return 0;
}