LOJ2542 - 「PKUWC2018」随机游走

考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

代码:

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
// =================================
// author: memset0
// date: 2019.01.14 10:09:31
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 20, mod = 998244353;
int n, m, t, s, S, lim, f[N], k[N], b[N], a[1 << 18];
std::vector <int> G[N];

inline int sum(int a, int b) { return (a + b) % mod; }
inline int dec(int a, int b) { return (a - b + mod) % mod; }
int inv(int x) { return !x || x == 1 ? 1 : (ll)(mod - mod / x) * inv(mod % x) % mod; }

void dfs(int u, int father = 0) {
for (auto v : G[u]) if (v != father) dfs(v, u);
if ((1 << (u - 1)) & S) { k[u] = b[u] = 0; return; }
int Sk = 0, Sb = 0, d = G[u].size();
for (auto v : G[u]) if (v != father) (Sk += k[v]) %= mod, (Sb += b[v]) %= mod;
k[u] = inv(dec(d, Sk)), b[u] = (ll)k[u] * sum(Sb, d) % mod;
}
void dfs2(int u, int father = 0) {
f[u] = ((ll)k[u] * f[father] + b[u]) % mod;
for (auto v : G[u]) if (v != father) dfs2(v, u);
}

int calc(int _S) {
S = _S, dfs(s), dfs2(s);
return f[s];
}

void fwt(int *a) {
for (int len = 1; len < lim; len <<= 1)
for (int i = 0; i < lim; i += (len << 1))
for (int j = 0; j < len; j++)
(a[i + j + len] += a[i + j]) %= mod;
}

void main() {
read(n), read(m), read(s), lim = 1 << n;
for (int i = 1, u, v; i < n; i++) read(u), read(v), G[u].push_back(v), G[v].push_back(u);
for (S = 1; S < lim; S++) a[S] = (ll)calc(S) * (__builtin_popcount(S) & 1 ? 1 : mod - 1) % mod;
fwt(a);
for (int i = 1; i <= m; i++) {
int S = 0; read(t);
for (int i = 1, x; i <= t; i++) read(x), S |= 1 << (x - 1);
print(a[S], '\n');
}
}

} signed main() { return ringo::main(), 0; }

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×