P5643 [PKUWC2018] 随机游走 题解
hunction
·
·
题解
不会 Min-max 容斥，然后想出来一个树上解方程 + 分层图 DP 的做法，看到题解区好像没有，于是来写一发。
首先我们设计一个平平无奇的 DP：
那么 $f(u, S) = \frac{f(fa_u, S - \{fa_u\}) + 1}{deg_u} + \sum\limits_{v \in son_u} \frac{f(v, S - \{v\}) + 1}{deg_u}$。
（注：$S - \{v\}$ 中的减号是差集，即 $v$ 不在 $S$ 中就返回 $S$）。
其中 $deg_u$ 是 $u$ 的度数，边界是 $f(x, \varnothing) = 0$。
这个 DP 没法直接转移，因为 $S - \{v\}$ 不一定小于 $S$（$v$ 可能不在 $S$ 内）。
所以我们对 $S$ 进行分层，外层从小到大枚举 $S$，那么转移时如果 $S - \{v\} \subset S$ 就可以把 $f(v, S - \{v\})$ 视为常数，否则就在同层中解一下方程。
剩下的就是树上解方程的内容了，为了方便起见，令 $g(u) = f(u, S)$，$S$ 为当前枚举到的集合。
现在我希望把所有的 $g(u)$ 都表示成 $k_u g(fa_u) + b_u$。
对于叶节点 $u$ 来说，$g(u) = g(fa_u) + 1$。
对于非叶节点 $u$ 来说，儿子都可以表示为 $k_vg(u) + b_v$，所以 $g(u)$ 可以表示成 $t_u g(u) + k'_ug(fa_u) +b'_u$ 的形式，然后移项就可以表示成 $k_u g(fa_u) + b_u$ 了。
对于根来说，根没有父亲，所以 $g(rt) = t_{rt} g(rt) + b_{rt}$。于是我可以解出 $g(rt)$。又因为剩下的每个点都表示成了 $k_u g(fa_u) + b_u$，所以所有 $g(u)$ 都被解出来了。
代码挺好写的，就是常数有点大，但是并不需要怎么卡常。
```cpp
#include <bits/stdc++.h>
using lld = long long;
const int N = 21, NS = (1 << 18) + 5, P = 998244353;
int n, Q, rt, curS;
lld F[N][NS], fc[N], K[N], T[N], B[N], C[N];
std::vector<int> to[N];
lld Qpow(lld a, lld p = P - 2) {
lld x = 1;
for (; p; p >>= 1, a = a * a % P)
if (p & 1) x = a * x % P;
return x;
}
void DFS(int u, int f) {
T[u] = 1;
for (int v : to[u])
if (v != f) {
DFS(v, u);
if (curS >> v & 1)
(B[u] += fc[u] * (F[v][curS & ~(1 << v)] + 1) % P) %= P;
else
(B[u] += fc[u] * (B[v] + 1) % P) %= P, (T[u] -= fc[u] * K[v] % P) %= P;
}
if (~f) {
if (curS >> f & 1)
(B[u] += fc[u] * (F[f][curS & ~(1 << f)] + 1) % P) %= P;
else (K[u] += fc[u]) %= P, (B[u] += fc[u]) %= P;
lld c = Qpow(T[u]);
(K[u] *= c) %= P, (B[u] *= c) %= P;
} else
F[u][curS] = B[u] * Qpow(T[u]) % P;
}
void GET(int u, int f) {
for (int v : to[u])
if (v != f)
F[v][curS] = (K[v] * F[u][curS] % P + B[v]) % P, GET(v, u);
}
int main() {
scanf("%d%d%d", &n, &Q, &rt), --rt;
for (int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
++fc[--u], ++fc[--v];
to[u].push_back(v);
to[v].push_back(u);
}
for (int i = 0; i < n; i++) fc[i] = Qpow(fc[i]), F[i][0] = 0;
for (int s = 1; s < (1 << n); s++) {
curS = s;
memset(K, 0, sizeof K);
memset(B, 0, sizeof B);
memset(T, 0, sizeof T);
DFS(rt, -1);
GET(rt, -1);
}
while (Q--) {
int k, s = 0;
scanf("%d", &k);
for (int i = 1, x; i <= k; i++) {
scanf("%d", &x);
s |= 1 << --x;
}
printf("%lld\n", (F[rt][s & ~(1 << rt)] + P) % P);
}
return 0;
}