[LOJ2542] 「PKUWC2018」随机游走（期望DP）

题意

• 给你一个$n$个点的树，询问从$s$号点出发，每次等概率选择一个相邻的点移动，求把集合$S$每个点至少访问一次的期望步数。

首先我们很自然设$f[u][S]$为从$u$号点出发访问$S$集合至少一次的期望步数，那么我们可以写出DP方程：
$$\begin{gathered} f[u][S]=\frac{1}{de[u]}\sum _{edge(u,v)}(f[v][S]+1)(u\notin S) \\ f[u][S]=\frac{1}{de[u]}\sum _{edge(u,v)}(f[v][S-u]+1)(u\in S) \end{gathered}$$

我们发现每个集合$S$要么从比它小的集合转移来，要么从它自己转移来，这个东西你从小到大枚举集合套高斯消元求解的话就是$O(2^n{n}^3)$的，但这个复杂度显然不靠谱，考虑优化。方便起见，以下用$f[u]$表示$f[u][S]$。

考虑一类期望DP的套路，我们把$f[u]$写成$A_u\times f[fa[u]]+B_u$的形式。先特判$u=S$的情况，这个时候很显然$A_u=B_u=0$，剩下的情况我们代回那个方程去解系数：
$$\begin{gathered} f[u]=\frac{f[fa[u]]}{de[u]}+\sum _{u=fa[v]}\frac{f[v][S]}{de[u]}+1(u\notin S) \\ f[u]=\frac{f[fa[u]]}{de[u]}+\sum _{u=fa[v]}\frac{A_{v}f[u]+B_v}{de[u]}+1(u\notin S) \\ f[u]de[u]=f[fa[u]]+\sum _{u=fa[v]}{A}_{v}f[u]+B_v+1(u\notin S) \\ f[u]=\frac{1}{de[u]-\sum A_v}\times f[fa[u]]+\frac{\sum B_v+de[u]}{de[u]-\sum A_v}(u\notin S) \end{gathered}$$
$u\notin S$的情况更简单，因为它转移用到的信息都是算出来的，那么直接令：
$$A_u=0,B_u=\frac{1}{de[u]}\sum _{edge(u,v)}(f[v][S-u]+1)$$

我们最后往回代计算DP值就好了，复杂度$O(n{2}^n)$。

#include <bits/stdc++.h>

#define pb push_back
#define SZ(x) ((int)x.size())
#define For(i, a, b) for (int i = a; i <= b; ++ i)

using namespace std;

const int N = 18 + 3; 
const int M = 1 << 18;
const int mod = 998244353;

vector<int> G[N];

int f[N][M], A[N][M], B[N][M], de[N];

int qpow(int a, int x) {
	int ret = 1; 
	while (x) {
		if (x & 1) ret = 1ll * ret * a % mod;
		x >>= 1, a = 1ll * a * a % mod;
	}
	return ret;
}

void dfs(int u, int dad, int S) {
	for (auto v : G[u]) if (v ^ dad) dfs(v, u, S);
	if ((1 << (u - 1)) & S) {
		A[u][S] = 0;
		if (__builtin_popcount(S) == 1) 
			return (void)(B[u][S] = 0);
		for (auto v : G[u]) 
			(B[u][S] += f[v][S ^ (1 << (u - 1))] + 1) %= mod;
		B[u][S] = 1ll * B[u][S] * qpow(de[u], mod - 2) % mod;
	} else {
		A[u][S] = B[u][S] = de[u];
		for (auto v : G[u]) if (v ^ dad) {
			(A[u][S] += mod - A[v][S]) %= mod;
			(B[u][S] += B[v][S]) %= mod;
		}
		A[u][S] = qpow(A[u][S], mod - 2);
		B[u][S] = 1ll * B[u][S] * A[u][S] % mod;
	}
}

void DFS(int u, int dad, int S) {
	f[u][S] = (1ll * A[u][S] * f[dad][S] % mod + B[u][S]) % mod;
	for (auto v : G[u]) if (v ^ dad) DFS(v, u, S);
}

int main() {

	freopen("2542.in", "r", stdin);
	freopen("2542.out", "w", stdout);

	int x, y, z, n, q, s;

	scanf("%d%d%d", &n, &q, &s);
	For(i, 2, n) {
		scanf("%d%d", &x, &y);
		G[x].pb(y), G[y].pb(x);
	}

	int all = 1 << n;
	For(i, 1, n) 
		de[i] = SZ(G[i]);
	For(i, 1, all - 1) {
		dfs(1, 0, i);
		DFS(1, 0, i);
	}

	For(i, 1, q) {
		scanf("%d", &x), z = 0;
		For(j, 1, x) {
			scanf("%d", &y);
			z |= 1 << (y - 1);
		}
		printf("%dn", f[s][z]);
	}

	return 0;
}

最后

以上就是彩色棒棒糖为你收集整理的[LOJ2542] 「PKUWC2018」随机游走（期望DP）的全部内容，希望文章能够帮你解决[LOJ2542] 「PKUWC2018」随机游走（期望DP）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。