详细揭秘:特殊图高斯消元

· · 算法·理论

树上高斯消元

给你一颗树,某些点为终止结点,求从每个点开始随机游走走到某个终止节点的期望时间。

从叶子开始将 f(u) 表示为 k(u)f(\text{fa}(u))+b(u),带回 f(\text{fa}(u)) 的方程中将 f(u) 消掉即可。

DAG 上高斯消元

可重集 / reset

有一个可重集 S,每一个时刻:

  • p 的概率执行以下操作:如果 S=\varnothing,则无事发生,否则会从 S 中删去恰好一个 \min(S)
  • 否则执行以下操作:如果 S=\varnothing,则会随机一个 x\in[1,n] 加入 S 中,否则会随机一个 x\in[1,\min(S)] 加入 S 中。

给定 n,mq 次询问给出一个初始的 S,问期望什么时刻 \text{sum}(S) 第一次大于 m

f(S) 为答案,则有:

f(S)=1+pf(S\setminus\min(S))+\dfrac{1-p}{\min(S)}\sum_{i=1}^{\min(S)}f(S\cup i)

使用树上高斯消元可得 40 分。

观察到转移只与 \text{sum}(S),\min(S) 有关,即对于所有 \text{sum}(S),\min(S) 相同的 S,它们转移的方式非常相似,考虑将它们压缩起来。我们设 f(i,j) 表示和为 i,最小值为 j 时的答案,则:

f(i,j)=1+pf(i-j,?)+\frac{1-p}{j}\sum_{x=1}^{j}f(i+x,x)

其中 f(i-j,?) 是不确定的:类比递归,调用者知道被调用者是谁,被调用者不知道调用者是谁。此处 f(i,j) 调用了 f(i+x,x)

下面归纳证明:存在确定的 k(i,j)b(i,j),使得对于任意的 f(i-j,?) 均有 f(i,j)=k(i,j)f(i-j,?)+b(i,j)

&=1+p f(i-j,?)+\frac{1-p}{j}\sum_{x=1}^{j}\left[k(i+x,x)f(i,j)+b(i+x,x)\right]\end{aligned}

移项得

k(i,j)=\dfrac{p}{1-\frac{1-p}{j}\sum_{x=1}^{j}k(i+x,x)} b(i,j)=\dfrac{1+\frac{1-p}{j}\sum_{x=1}^j b(i+x,x)}{1-\frac{1-p}{j}\sum_{x=1}^{j}k(i+x,x)} $$f(\varnothing)=\frac{1+\frac{1-p}{n}\sum_{x=1}^n b(x,x)}{1-p-\frac{1-p}{n}\sum_{x=1}^n k(x,x)}$$ 对于给定的初始集合 $S$,加入元素的顺序一定是从大到小。设 $S$ 从大到小排序后为 $a_{1\sim k}$,前缀和为 $b_{1\sim k}$, 递归 $f(b_k,a_k)=k(b_k,a_k)\times f(b_{k-1},a_{k-1})+b(b_k,a_k)$ 就能求出答案。 使用离线线性求逆可以做到 $O(nm+q)$。 更平凡地, > 给你一个有向无环图,出度为 $0$ 的点为终止结点,求从每个点开始随机游走走到某个终止节点的期望时间。 > > 随机游走的规则为:对于每一次,设当前在点 $u$,有 $p_u$ 的概率回退上一步游走以及 $1-p_u$ 的概率进行一次游走,以 $w_{u,v}$ 为权随机一条边 $u\to v$ 游走到点 $v$。 ## ACAM 上高斯消元 > #### [字符串 / string](http://192.168.102.138/JudgeOnline/problem.php?cid=2001&pid=0) > > 给你 $n$ 个长为 $m$、字符集为 $k$ 的字符串 $T_{1\sim n}$,以及一个长为 $k$ 的序列 $p_{1\sim k}$,每次询问给一个字符串 $S$,在 $S$ 后面以 $p$ 为概率随机添加字符直到恰好包含任意一个 $T_i$,求期望添加字符数量。 > > $n,m\le 100$,$k\le 10^9$。 建出 ACAM,由于字符集大,我们不复制转移,当需要转移 $(x,t,c)$ 这样一条边时从 $\text{fail}(x)$ 开始暴力跳 $\text{fail}$ 直到存在 $c$ 转移边即可。考虑一个串在 Trie 树上形成的一条链,显然每次跳 $\text{fail}$ 都会使深度变小至少 $1$,而转移一个字符深度至多增加 $1$,所以这部分均摊复杂度 $O(nm\log k)$。 不妨先考虑字符集 $k$ 较小的时候怎么做。设 $g_{u,c}$ 表示从节点 $u$ 添加转移 $c$ 到达的点,$f(u)$ 为从 $u$ 开始游走需要的期望时间。 $$f(u)=1+\sum_{c}f(g_{u,c})p_c$$ 暴力高消只能做到 $O(n^3m^3+nmk)$。 一个思路为取若干变量为关键变量,使得其它变量都可以通过关键变量的线性组合加一个常数来表示。对于这个问题,对于 Trie 树上所有儿子数量 $\text{son}(u)\ge 2$ 的结点 $u$,我们将所有 $u$ 的儿子 $v$ 对应的变量 $f(v)$ 设为关键变量。除此之外,再将 $f(0)$ 设为关键变量。 接下来我们需要将所有非关键变量用关键变量表示。我们按深度从小到大考虑,对于结点 $u$,由于它是非关键变量,所以它的父亲 $t$ 只有它一个儿子,设 $u$ 到父亲的边上的字符为 $c$。 $$f(t)=1+f(u)p_c+\sum_{i\ne c}f(g_{t,i})p_i$$ 由于 $t$ 只有 $u$ 一个儿子,后面那部分都是已经表示过的,所以可以直接表示出 $f(u)$。 考虑关键变量数量,由于叶子只有 $O(n)$ 个,每一次出现大于一个儿子就会多出现对应数量的叶子,所以关键变量只有 $O(n)$ 个。 再考虑如何将关键变量消元。设有 $l$ 个关键变量,则必然剩余 $l$ 个方程: - 对于 $\text{son}(u)\ge 2$: $$f(t)=1+\sum_{i}f(g_{t,i})p_i$$ - 对于 $\text{son}(u)=0$: $$f(u)=0$$ 时间复杂度 $O(n^2mk+n^3)$,不够优秀。 考虑将 $k$ 去掉。对于表示 $f(u)$ 的部分: $$f(u)=\dfrac{f(t)-\sum_{i\ne c}f(g_{t,i})p_i-1}{p_c}$$ 若 $t=0$,则 $$f(u)=f(t)-\dfrac{1}{p_c}$$ 否则 $$f(u)=\dfrac{f(t)-f(\text{fail}(t))}{p_c}+f(\text{fail}(u))$$ 对于求解关键变量列方程的部分: $$\begin{aligned}f(t)&=1+\sum_{c}f(g_{t,c})p_c\\ &=1+\sum_{c\in\text{son}(t)}f(g_{t,c})p_c+\sum_{c\notin\text{son}(t)}f(g_{\text{fail}(t),c})p_c\\ &=f(\text{fail}(t))+\sum_{c\in\text{son}(t)}\left[f(g_{t,c})-f(\text{fail}(g_{t,c}))\right]p_c \end{aligned}$$ 时间复杂度成功优化成 $O(n^2m+n^3)$。