LOJ#2542. 「PKUWC 2018」随机游走(min-max容斥+树上高斯消元)

题目描述

给定一棵 $n(n<=18)$ 个结点的树,你从点 $x$ 出发,每次等概率随机选择一条与所在点相邻的边走过去。

有 $Q(Q<=5000)$ 次询问,每次询问给定一个集合 $S$,求如果从 $x$ 出发一直随机游走,直到点集 $S$ 中所有点都至少经过一次的话,期望游走几步。

特别地,点 $x$(即起点)视为一开始就被经过了一次。

答案对 $998244353$ 取模。

Solution

这题首先我们要知道min-max容斥。

我们可以试着可以证明:

首先我们将$x$从小到大排序,则有$$max\left\{x_1,x_2,…x_n\right\}=\sum_{i=1}^{n}\sum_{j=0}^{n-i}(\binom{n-i}{j}*(-1)^{j+2})*x_i$$

即我们算每一个$x_i$的贡献,枚举最小的$x_i$,然后在$i$后面选任意多数,那么最小值为$x_i$。

然后我们发现中间的$\sum_{j=0}^{n-i}(\binom{n-i}{j}*(-1)^{j+2})$只在$n-i=0$时为$1$,其余情况和均为$0$,所以我们发现这个式子的结果最终等于$x_n$,即$max\left\{x_1,x_2,…x_n\right\}$。

那么我们回到这题,令$Ci$为第i个点到达的时刻。

令$E[max\left\{S\right\}]=\max_{i\in S}c[i]$,$E[min\left\{S\right\}]=\min_{i\in S}c[i]$。

$$E[max\left\{S\right\}]=\sum_{S’\subseteq S}(-1)^{\left|S’\right|+1}*E[min\left\{S’\right\}]$$

那么要求的就是$E[max\left\{x_1,x_2,…x_t\right\}]$,所以我们只要求出$E[min\left\{x_1,x_2,…x_t\right\}]$即到达集合中任意一个点就停止的期望步数即可。

这时我们可以列出每个点的期望方程,令$f[i]$表示第i个点的期望步数,那么有

若u点不为根且u点不为停止点,则$f[u]=\frac{\sum_{v}(f[v]+1)}{deg[u]}+\frac{f[fa[u]]+1}{deg[u]}$;

若u点为根,则$f[u]=\frac{\sum_{v}(f[v]+1)}{deg[u]}$;

若u点为停止点,则$f[u]=0$。

那么我们可以用$O(n^3)$的高斯消元来做,但我们有更好的办法。

对于树上高斯消元,我们有一种类似与树型DP的做法,即用fa[u]来表示u。

我们发现u的儿子可以被u表示,那么在上面的式子中,未知数即为$f[u]$和$f[fa[u]]$,那么我们便可以用$f[u]=a[u]*f[fa[u]]+b[u]$来表示$f[u]$。

从上面的式子我们可以推得

$$f[u]=\frac{\sum_{v}(a[v]*f[u]+b[v]+1)}{deg[u]}+\frac{f[fa[u]]+1}{deg[u]}$$
$$(deg[u]-\sum_{v}a[v])f[u]=\sum_{v}(b[v]+1)+f[fa[u]]+1$$
$$f[u]=\frac{1}{deg[u]-\sum_{v}a[v]}*f[fa[u]]+\frac{\sum_{v}(b[v]+1)+1}{deg[u]-\sum_{v}a[v]}$$
所以我们把$f[u]$化成了$f[u]=a[u]*f[fa[u]]+b[u]$的形式。

最终我们要求的即为$f[root]=\frac{\sum_{v}(b[v]+1)}{deg[root]-\sum_{v}a[v]}$,那么用上面的方法计算即为$b[root]$。

这样我们就解决了这道题,时间复杂度$O(n*2^n+Q*n)$。

 

点赞
  1. Orz说道:

    太强了,我好害怕啊 :confused:
    怎么都是我听不懂的东西

  2. PhoenixGS说道:

    前排膜大佬

Orz进行回复 取消回复

您的电子邮箱地址不会被公开。