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

· · 算法·理论

树上高斯消元

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

从叶子开始将 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,m，q 次询问给出一个初始的 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)$。