Luogu3251 [JLOI2012]时间流逝

博主： tony102
发布时间：2021 年 03 月 11 日
1563 次浏览
暂无评论
2003字数
分类：题解

[Link](https://www.luogu.com.cn/problem/P3251)

## Sol

学习树上高斯消元

这个玩意儿，非常简单！！！只需要初中代换功底，你就可以掌握！！因为这不是什么高斯消元（其实也算，但是介于只有两个元消都只需要消一次，代回也只有一次，所以就像是在算式子一样

设 $f(S)$ 表示到达当前集合$S$的期望步数。暴力枚举前驱状态，记为 $pre$， 选出$\leq min$ 然后达到的**后继集合所形成的集合**记为$nxt_S$，其中每一个后继集合满足$\sum_{v \in nxt_S} f(nxt_v) = nxt_S$

那么可以得到暴力转移：

$$f(S) = 1 + p\times f(pre) + \frac{1-p}{|nxt_S|} \sum_{v \in nxt_S} f(nxt_v)$$

$|nxt_S|$表示能够后继集合所形成的集合的大小。

这个式子表达的意思就是，从$pre$集合转移到当前这个集合，需要$1$步，再加上有$p$的概率删除$pre$集合中的一个数所需要的步数$f(pre)$ 。最后还有从所有后继集合中选出一个，这个是$\frac{1}{|nxt_S|}$ ，有$1-p$的概率加进来一个数，再乘上到达后继集合的期望步数$f(nxt_v)$

现在来做”树上高斯消元“。对于一个集合$S$，删除$S$中的一个元素后的集合就是$pre$，因此$pre$是唯一确定的。但是每次加进去的数$x$都只满足$x \leq min_s$ ，  $min_s$ 表示$S$中最小的元素。所以后继状态$nxt$可能有多个。我们把$pre$看做$S$的父亲，$nxt_v$ 看做$S$的儿子。那么转移之间构成一棵树。所以叫做树上高斯消元。

那么我们想，假如我们可以把$f(S)$表示成一个高斯消元的一般形式，也就是未知元全部在左边，常数项留在右边的形式。更加具体地，可以被表示为

$f(S) = k \times f(pre) + b$

的形式。

那么$f(S)$仅跟父亲($f(pre)$) 和儿子的状态相关。从底向上操作，把每个儿子也表示成这种形式，就可以代入消元。比如说，对于一个叶子节点，没有跟儿子相关的项，那么叶子的期望可以被直接计算。叶子是父亲的未知元中的一项，现在它被解出来了，也就可以在父亲的未知元中被消去。

具体地，我们来看一下是怎么操作的。

把常数项全部留在右边

$$f(S) - p\times f(pre) - \frac{1-p}{|nxt_S|} \sum_{v \in nxt_S} f(nxt_v)  = 1$$

$\frac{1-p}{|nxt_S|}$ 是一个常量，我们记$C = \frac{1-p}{|nxt_S|}$

把$f(s)$表示成上面那种形式，我们先把$f(nxt)$也就是它的子节点写成那种形式。为了方便，我们记$a_k(S) = \sum_{v \in nxt_S} k_v$

$a_b(S) = \sum_{v \in nxt_S} b_v$

现在就变成了
$$f(S) - p \times f(pre) - C\times a_k(S)f(S)- C \times a_b(S) = 1$$

对于$f(S)$这一项，有可以系数提前

$(1 - C \times a_k(S)) f(S) = 1 + p \times f(pre) + C \times a_b(S)$

系数化为$1$，直接除过去

$$f(S) = \frac{p \times f(pre)}{1 - C \times a_k (S)} + \frac{1 + C \times a_b(S)}{1 - C \times a_k (S)} $$

现在我们只要从低至上，依次算出$a_b (S)$ 和 $a_k (S)$ ，给当前节点的$k, b$ 对应加上子节点贡献上来的就可以了

代码也非常简单，一看就懂

## Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 50 + 5;

double p;
int t, n, a[SIZE];

int read() {
	char ch = getchar(); int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}

pair < double, double > dfs(int sum, int mi) {
	if (sum > t) return make_pair(0.00, 0.00);
	double k = 0.00, b = 0.00, g = (1 - p) / mi;
	for (int i = 1; i <= mi; ++ i) {
		pair < double, double > nxt = dfs(sum + a[i], i);
		k += nxt.first, b += nxt.second;
	}
	if (!sum) g = 1.00 / mi;
	return make_pair(p / (1.00 - g * k), (1.00 + g * b) / (1.00 - g * k));
}

int main() {
	// freopen("code.in", "r", stdin);
	while (~scanf("%lf", &p)) {
		t = read(), n = read();
		for (int i = 1; i <= n; ++ i) a[i] = read();
		std::sort(a + 1, a + n + 1);
		printf("%.3lf\n", dfs(0, n).second);
	}
	return 0;
}
```

最后修改：2021 年 08 月 20 日