LibreOJ 2542 「PKUWC2018」随机游走

发表于 | 分类于

Description

有一个\(n\)个点的树，有一个固定的点为\(x\)。

\(Q\)次询问，每次给你一个集合。要求你求出从\(x\)出发，每一步都等概率随机选择一条邻边走过去，将集合中每个点都走了至少一遍的话期望的步数为多少（\(x\)视为一开始就经过了）。答案模\(998244353\)输出。

\(1\leq n\leq 18, Q\leq 5000\)。

Solution

高，高啊.jpg

考虑期望步数的实质是集合中最晚一个经过的点被经过的期望步数。最大值不好算，我们就考虑用MIN-MAX容斥，转成最小值。因此问题转化成了从\(x\)出发最早走到一个集合中至少一个点的期望步数。

这个东西的话，先枚举那个集合\(S\)，然后考虑期望DP。设状态\(f_i\)表示从\(i\)出发的期望步数，那么有： \[ f_i = \begin{cases} 0 & \text{if } i\in S,\\ \frac{f_{\mathrm{fa}_i}+\sum f_{\mathrm{ch}_{i, j}}}{d_i} + 1 & \text{if }i\notin S. \end{cases} \] 其中\(\mathrm{fa_i}\)表示\(i\)的父亲，\(\mathrm{ch}_{i, j}\)表示\(i\)的第\(j\)个儿子，\(d_i\)表示\(i\)的度数。如果这样直接高消做的话，那么DP+高消部分的复杂度是\(O(2^nn^3)\)，有点吃不消（但据说可以过的）。

考虑到这样一件事：对于任意叶子或者是属于\(S\)的点，他们的\(f\)都可以表示为父亲的\(f\)的若干倍加上一个常数。那么我们DFS一遍，一个只有这两类点儿子的父亲\(i\)在DFS完了自己所有儿子之后，就能知道\(\sum f_{\mathrm{ch}_{i, j}}\)这个东西可以如何用\(f_i\)的若干倍加上一个常数来表示，这样一来移项再整理一下\(f_i\)也就可以用\(f_{\mathrm{fa}_i}\)的若干倍加上一个常数来表示了。如此往上一直推，推到根节点的话根节点的父亲的答案为0，所以最终答案就是那个最后的常数了。

Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

struct Rec {
  ll x, y;
  Rec(ll a = 0, ll b = 0) { x = a; y = b; }
};
Rec operator +(const Rec &a, const Rec &b) {
  return Rec((a.x + b.x) % ha, (a.y + b.y) % ha);
}
Rec operator -(const Rec &a, const Rec &b) {
  return Rec((a.x - b.x + ha) % ha, (a.y - b.y + ha) % ha);
}
Rec operator *(const Rec &a, const ll &v) {
  return Rec(a.x * v % ha, a.y * v % ha);
}
Rec operator *(const ll &v, const Rec &a) {
  return Rec(a.x * v % ha, a.y * v % ha);
}

const int maxn = 20;
std::vector<int> G[maxn]; int deg[maxn];
Rec dfs(int s, int x, int fa) {
  if((1 << (x - 1)) & s) return Rec();
  Rec lt(deg[x], ha - deg[x]);
  for(int v : G[x]) {
    if(v != fa) {
      lt = lt - dfs(s, v, x);
    }
  }
  ll inv_A = inv(lt.x);
  return Rec(inv_A, ((ha - lt.y) % ha) * inv_A % ha);
}

ll minv[1 << 18], ps[1 << 18];
int cnt[1 << 18];
ll dir(int x) {
  if(x & 1) {
    return 1;
  } else {
    return ha - 1LL;
  }
}
int main() {
  int n, Q, x; scanf("%d%d%d", &n, &Q, &x);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
    deg[u] ++; deg[v] ++;
  }
  for(int s = 1; s < (1 << n); s ++) {
    minv[s] = dfs(s, x, -1).y;
  }
  for(int s = 1; s < (1 << n); s ++) {
    for(int i = 0; i < n; i ++) {
      if((1 << i) & s) cnt[s] ++;
    }
  }
  while(Q --) {
    int k; scanf("%d", &k);
    int s = 0;
    while(k --) {
      int x; scanf("%d", &x);
      s |= (1 << (x - 1));
    }
    ll ret = 0;
    for(int t = s; t; t = (t - 1) & s) {
      ret = (ret + (dir(cnt[t]) * minv[t]) % ha) % ha;
    }
    printf("%lld\n", ret);
  }
  return 0;
}