LOJ #2542. 「PKUWC 2018」随机游走(最值反演 + 树上期望dp)

92 阅读 0 评论 61 点赞

我是靠谱客的博主健壮黑裤，最近开发中收集的这篇文章主要介绍LOJ #2542. 「PKUWC 2018」随机游走(最值反演 + 树上期望dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原文地址为： LOJ #2542. 「PKUWC 2018」随机游走(最值反演 + 树上期望dp)

写在这道题前面 : 网上的一些题解都不讲那个系数是怎么推得真的不良心 TAT
(不是每个人都有那么厉害啊 , 我好菜啊)
而且 LOJ 过的代码千篇一律 ... 那个系数根本看不出来是什么啊 TAT
后来做了 HDU 4035 终于会了.... 感谢雕哥的帮助 !!!

题意 : #2542. 「PKUWC 2018」随机游走
题解 :

原本的模型好像我不会那个暴力dp .... 就是直接统计点集中最后经过的点的期望 , 也就是点集中到所有点步数最大值的期望 . (也许可以列方程高斯消元 ? 似乎没分)

但我们考虑转化一下 (因为原来有道CLJ的题也是求这个) 把最大值的期望用 最值反演(MinMax容斥) 转化成最小值的期望就可以算了 ...

最值反演 (又称 MinMax容斥 ) :

[displaystyle max{S}=sum_{Tsubseteq S}(-1)^{|T|-1}min{T}]

其中 (S) 是全集 , (T) 是它的一个子集 , 就有这个神奇的定理 ...

证明 ( 来自 DOFY大大的博客 ) :

设最大值为 (x in S) ，那么构造映射 (f(T) to x in T~?~T−x:T+x) ，也就是有 (x) 就去掉，没有就加上。那么当 (T) 不为空和 ({x}) 时，(T) 与 (f(T)) 因为只相差一个最大值，最小值肯定相同，集合大小只相差 (1) ，就抵消了（一一映射），因为空集没有最小值，所以最后只剩下 ({x}) 的贡献。

然后有了这个 , 每次我们只需要求经过点集中点步数最少的贡献 .

假设我们当前有一个集合 (S) , 我们用 (f(u)) 表示从 (u) 出发 , 第一次访问 (S) 中节点的期望步数 .

所以我们有一些显然的式子 :

(u in S:)

[f(u)=0]
(u not in S:)

令 (d[u]) 为 (u) 在树上的度数(连出来边数) , (mathrm{ch}[u]) 为 (u) 的儿子 , (mathrm{fa}[u]) 为 (u) 的父亲 .

[displaystyle f(u)=[f(mathrm{fa}[u])+1+sum (f(mathrm{ch[u]})+1)] times frac{1}{d[u]}]

[displaystyle =frac{1}{d[u]}f(mathrm{fa}[u])+frac{1}{d[u]}sum f(mathrm{ch}[u])+1]

不难发现每个点的答案可以只保留它父亲的答案和一个常数的贡献

( 可以理解成全都能倒推回去 , 因为那个就算没有 (u in S) 的限制 , 叶子的贡献也只与父亲有关 )

假设令它为 [f(u)=A_uf(mathrm{fa}[u])+B_u] 以及 (v = mathrm{ch}[u])

那么有 [displaystyle sum f(mathrm{ch[u]})=sum f(v) = sum(A_v f_u + B_v)]

把这个回代就有

[displaystyle (1-frac{sum A_v}{d[u]}) f(u) = frac{1}{d[u]}f(mathrm{fa}[u])+(1+frac{B_v}{d[u]})]

除过去就可以得到每个递推式的 (A,B) 了 qwq

然后随便写写就行啦 , 复杂度 (O((n+Q) cdot 2^n)) ... 其实后面那个复杂度是对于每个询问枚举子集 .

预处理的话 , 复杂度就变成 (O(ncdot 2^n + 3^n)) 啦 ...

似乎都可以轻松过掉 ?

代码 :

#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * fh;
}

void File() {
#ifdef zjp_shadow
    freopen ("2542.in", "r", stdin);
    freopen ("2542.out", "w", stdout);
#endif
}

typedef long long ll;
const int Mod = 998244353;

inline ll fpm(ll x, int power) {
    ll res = 1; x = (x % Mod + Mod) % Mod;
    for (; power; power >>= 1, (x *= x) %= Mod)
        if (power & 1) (res *= x) %= Mod;
    return res;
}

const int N = 20; 
int n, Q, rt, d[N];
vector<int> G[N]; ll A[N], B[N], invd[N];

void Dp(int u, int fa, int S) {
    if ((1 << (u - 1)) & S) { A[u] = B[u] = 0; return ; }

    ll totA = 0, totB = 0;
    for (int v : G[u]) if (v ^ fa)
        Dp(v, u, S), totA += A[v], totB += B[v];
    totA %= Mod, totB %= Mod;

    ll coef = fpm(Mod + 1 - totA * invd[u], Mod - 2);
    A[u] = invd[u] * coef % Mod;
    B[u] = (1 + totB * invd[u] % Mod) * coef % Mod;
}

ll Minv[1 << 18]; int bit[1 << 18];

int main () {
    File();

    n = read(); Q = read(); rt = read();
    For (i, 1, n - 1) {
        int u = read(), v = read();
        G[u].push_back(v); G[v].push_back(u);
        ++ d[u]; ++ d[v];
    }
    For (i, 1, n) invd[i] = fpm(d[i], Mod - 2);

    int maxsta = (1 << n) - 1;
    For (i, 0, maxsta) {
        Dp(rt, 0, i);
        Minv[i] = B[rt];
        bit[i] = bit[i >> 1] + (i & 1);
    }

    while (Q --) {
        int k = read(), sta = 0;
        while (k --) sta |= (1 << (read() - 1));
        ll ans = 0;
        for (int i = sta; i; i = (i - 1) & sta)
            ans += (bit[i] & 1 ? 1 : -1) * Minv[i];
        ans = (ans % Mod + Mod) % Mod;
        printf ("%lldn", ans);
    }

    return 0;
}