LOJ #2542. 「PKUWC2018」随机游走

链接：[戳轻点 >_<](https://loj.ac/problem/2542)

神仙题啊！
还不自量力的想了半天。
看完题解发现自己更本没资格做这道题……

首先貌似有个没分的高斯消元？
嗯……全部都至少走一遍的期望根本不会算啊。

我们先来看一个很好理解的结论：

### 最值反演：
　　考虑任意集合$S$，元素$i$有点权$w_i$。
　　定义
　　$$min_S=\min_{u\in S}w_u,max_S=\max_{u\in S}w_u$$
　　那么有：
　　$$min_U=\sum_{S\subseteq U}(-1)^{|S|+1}max_{S}$$
　　$$max_U=\sum_{S\subseteq U}(-1)^{|S|+1}min_{S}$$
　　神奇吧~
　　~~并不~~
　　从组合意义解释这个东西：
　　为了方便我们只考虑$max$，$min$同理。
　　其实仔细想想就会发现，假设一个$max_S \neq max_U$，设最大的点为$v$，那么$min_{(S\cup \{v\})}=[S=\emptyset]?w_v:min_S$
　　因为假设原来不是空集，那么一定存在点$i$使得$w_i\le w_v$。不难发现两个集合$min$一样但是集合大小相差$1$，所以符号相反被抵消。
　　最后就只剩最大值产生贡献了。
　　
　　考虑期望具有线性，可以任意做加减法，假设我们知道$w_i$的期望$E(w_i)$，由于期望可加且最值反演仅用到加减法运算，所以有：
　　$$E(min_U)=\sum_{S\subseteq U}(-1)^{|S|+1}E(max_{S})$$
　　$$E(max_U)=\sum_{S\subseteq U}(-1)^{|S|+1}E(min_{S})$$
　　于是我们把最大值的期望变成了最小值的期望。
　　
现在我们重新回到这道题，发现其实集合$S$中的点每一个都至少走一遍的期望步数，其实就是集合中期望步数最大的点的期望步数。
那么用上最值反演，变成了求期望步数最小的点的期望步数，也就是走到集合中任意一个点的期望步数。
这个就变得稍微可求了一点。

然后才听说树上随机游走问题有个套路。
设$f_u$为根走到$u$的期望步数，那么$f_u$只和$f_{fa_u}$有线性关系，也就是存在$f_u=A_uf_{fa_u}+B_u$。
为什么呢？
首先考虑一个叶子只能由父亲转移过来，一定只和父亲有线性关系。
那么叶子的父亲也只和它的父亲有线性关系，因为叶子的期望都可以用自己表示，以此类推……

那么我们先列出比较显然的等式，设$d_u$为$u$的度数：
$$f_u=\frac{f_{fa_u}}{d_u}+\frac{\sum_{v\in son_u}f_v}{d_u}+1$$

直接算不好算，设线性关系为$f_u=A_uf_{fa_u}+B_u$。
我们将儿子$f$值的全部代换为设出的关系。
有：
$$f_u=\frac{f_{fa_u}}{d_u}+\frac{\sum_{v\in son_u}A_vf_{u}+B_v}{d_u}+1$$
化简可得：
$$f_u=\frac{f_{fa_u}}{d_u-\sum_{v\in son}A_v}+\frac{\sum_{v\in son}B_v+d_u}{d_u-\sum_{v\in son}A_v}$$
于是我们得到了所有$f_u$与$f_{fa_u}$的关系。
那么如果根为$x$，由于$f_0=0$，$f_x=B_x$，可以直接获得。
我们直接对每一个子集都这样计算一下经过其中任意一个点的期望步数，使用最值反演即可。

但是这里最值反演要枚举子集，复杂度为$O(3^n)$。
考虑$FMT$其实就是优化了的枚举子集。
我们先把$(-1)^{|S|+1}$的系数带上，然后做一遍$FMT$即可。
复杂度：$O(n2^n)$

```
#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int N = 20;
const int mod = 998244353;
struct edge {
	int v, next;
} e[(N << 1) + 5];
int head[N + 5], cnt, d[N + 5], bc[1 << N], rt, m, st;
int f[1 << N], A[N + 5], B[N + 5], n, u, v;

void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}

void dfs(const int &mask, const int &u, const int &p) {
	if(mask & (1 << u - 1)) 
		return A[u] = B[u] = 0, void();
	int sumA = 0, sumB = 0;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dfs(mask, v, u);
		Add(sumA, A[v]);
		Add(sumB, B[v]);
	}
	A[u] = fpow((d[u] - sumA + mod) % mod, mod - 2);
	B[u] = 1ll * ((sumB + d[u]) % mod) * A[u] % mod;
}

void FMT(int * A, int n) {
    for(int i = 1; i < (1 << n); i <<= 1)
        for(int p = i << 1, j = 0; j < (1 << n); j += p)
            for(int k = 0; k < i; ++k)
                Add(A[i + j + k], A[j + k]);
}

int main() {
	scanf("%d%d%d", &n, &m, &rt);
	for(register int i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v);
		adde(u, v), adde(v, u);
		++d[u], ++d[v];
	}
	for(register int i = 1; i < 1 << n; ++i)
		bc[i] = bc[i >> 1] + (i & 1);
	for(register int i = 1; i < 1 << n; ++i)
		dfs(i, rt, 0), f[i] = (bc[i] & 1) ? B[rt] : (mod - B[rt]);
	FMT(f, n);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d", &u), st = 0;
		while(u--) {scanf("%d", &v), st |= (1 << v - 1);}
		printf("%d\n", f[st]);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链