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:
    怎么都是我听不懂的东西

发表评论

电子邮件地址不会被公开。 必填项已用*标注