一类符合线性关系的 DP 的后效性处理

Gorenstein · 2023-03-21 15:15:19 · 算法·理论

本文介绍的利用 DP 转移的线性形式和转移边构成树形结构的性质来优化高斯消元 DP，有些地方称作“树上高斯消元”，是一类用途较广的 DP 优化策略。

本文中出现题目的题单

绝大多数 DP 的过程可以抽象为在一张图中跑最短/最长路或者对路径进行计数。\qquad\qquad\qquad\qquad\qquad\qquad\; 在有后效性的 DP 中，转移边不构成 DAG，这个时候就需要依据转移方程进行高斯消元一并求解。而对于一些特殊的转移形式，我们还可以将其优化至线性的时间。

引入：优化朴素高斯消元

下面由一个序列上的问题引入本文的正题。

CF24D Broken Robot

对于一行内的转移，DP 具有后效性。因此我们列出方程组如下：

\begin{pmatrix} -\frac{2}{3}&\frac{1}{3}&0&\cdots&0&0&0\\ \frac{1}{4}&-\frac{3}{4}&\frac{1}{4}&\cdots&0&0&0\\ 0&\frac{1}{4}&-\frac{3}{4}&\cdots&0&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&\cdots&\frac{1}{4}&-\frac{3}{4}&\frac{1}{4}\\ 0&0&0&\cdots&0&-\frac{2}{3}&\frac{1}{3} \end{pmatrix} \begin{pmatrix} f_1\\f_2\\f_3\\\vdots\\f_{n-1}\\f_n \end{pmatrix} =\begin{pmatrix} -1\\-1\\-1\\\vdots\\-1\\-1 \end{pmatrix}

我们发现每一行至多只有三个元素，因此可以在 O(n) 的时间内就完成消元。这是市面上流传较广的做法，我们来看看它具有什么特殊的性质。首先对于 f_1，它实质上给出了：

-\frac{2}{3}f_1+\frac{1}{3}f_2=-1,\quad f_1=\frac{1}{2}f_2+\frac{1}{2}

它是一个 f_1 关于 f_2 的一次式。如果我们将 f_1 代入第二行，我们就能同样将第二行消成仅剩两个变量：

\begin{aligned} \frac{1}{4}\left(\frac{1}{2}f_2+\frac{1}{2}\right)-\frac{3}{4}&f_2+\frac{1}{4}f_3&=\;&-1\\ &f_2&=\;&\frac{2}{5}f_3+\frac{8}{5} \end{aligned}

由此我们发现 f_2 也关于 f_3 成线性关系。依次类推，我们得出在消元过程中，f_i 与 f_{i+1} 皆满足关系：

f_i=k_if_{i+1}+b_i

现在我们将其推广，就得到本文着重介绍的处理方法。例如：

将很多条链接起来——形成了一颗树。
更一般地，对于一般的有后效性 DP，但是抽象出的转移边构成了树。

推广：一类复合线性关系的方程

对于以下一类 DP 方程，我们可以直接消除其后效性，达到 O(n)：

f_x=\gamma+\alpha f _{p(x)}+\beta\sum_{i=1}^{|\operatorname{suc}x|}\left(\tau_if_{y_i}+g_{y_i}\right)

也即要求：

转移结构形成一颗有根树，其中 p(x),(y_i)_{i\in\operatorname{suc}x} 分别为 x 的父状态和子状态；
关于 p(x) 和 (y_i)_{i\in\operatorname{suc}x} 的转移皆为线性形式。

则这类 DP 方程皆满足：

f_x=k_if_{p(x)}+b_i

线性关系的证明与递推方法

以上关于构成一棵有根树的条件说明了存在一些状态 y，满足 y 不存在后继状态，也即树上的叶子节点。对于这些 y，我们有 f_y=\alpha f_{p(y)}+\gamma。

以下使用数学归纳法证明，对于任意 x，其答案关于父状态的答案构成线性关系。

假设 x 的子状态 (y_i)_{i\in\operatorname{suc}x} 皆符合线性关系，考虑 f_x 与 f_{p(x)}：

\begin{aligned} f_x&=\gamma+\alpha f _p+\beta\sum_{i=1}^{|\operatorname{suc}x|}\left(\tau_if_{y_i}+g_{y_i}\right)\\ f_x&=\gamma+\alpha f_p+\beta\left(\tau_ik_{y_i}f_{x}+\tau_ib_{y_i}+g_{y_i}\right)\\ &=\gamma+\alpha f_p+\beta K_x'f_x+\beta B'_x+\beta G_x\\ (1-\beta K'_x)f_x&=\gamma+\alpha f_p+\beta\left(B'_x+G_x\right)\\ f_x&=\frac{\alpha}{1-\beta K'_x}f_p+\frac{\gamma+\beta(B'_x+G_x)}{1-\beta K'_x} \end{aligned}

其中 K'_x,B'_x 为：

K'_x=\sum_{i=1}^{|\operatorname{suc}x|}\tau_ik_{y_i},\quad B'_x=\sum_{i=1}^{|\operatorname{suc}x|}\tau_ib_{y_i},\quad G_x=\sum_{i=1}^{|\operatorname{suc}x|}g_{y_i}

我们就证明了这个结论。由此亦得出其系数乃是：

k_x=\frac{\alpha}{1-\beta K'_x},\quad b_x=\frac{\gamma+\beta(B'_x+G_x)}{1-\beta K'_x}

此时其系数已与父状态 p(x) 无任何关系，我们消除了后效性。据此即可 DP 出系数。对于根状态，显然有 f_{p(rt)}=K'_x=\gamma=0，从而：

f_{rt}=\beta(B'_x+G_x)

一些经典的题目

P5643 [PKUWC2018] 随机游走

这是直接在树上的情形。

直接套 \text{min-max} 容斥：

E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T))

那么我们只需求出 \min(T)。这个东西可以 DP，这里钦定 x_0 为根，设 f_{T,x} 表示从 x 出发到达 T 中任意一点的期望步数，F(x) 为其父节点，设 \deg x 表示 x 的边的个数，有转移：

f_{T,x}=\frac{1}{\deg x}\left(f_{T,F(x)}+\sum_{y\in\operatorname{son}x}f_{T,y}\right)+1

依据它就可以高消求出 f_{T,x_0} 了。但是这样是 O\!\left(n^32^n\right) 的。

接下来我们运用前述性质来优化这个 DP。

f_{T,x}=\frac{1}{\deg x}\left(f_{T,F(x)}+\sum_{i=1}^{\deg x-1}\left(k_{y_i}f_{T,x}+b_{y_i}\right)\right)+1

f_{T,x}\deg x=f_{T,F(x)}+A_xf_{T,x}+B_x+\deg x

f_{T,x}=\frac{1}{\deg x-K_x}f_{T,F(x)}+\frac{\deg x+B_x}{\deg x-K_x}

其中：

K_x=\sum_{y\in\operatorname{son}x}k_y,\quad B_x=\sum_{y\in\operatorname{son}x}b_y

那么：

k_x=\frac{1}{\deg x-K_x},\quad b_x=\frac{\deg x+B_x}{\deg x-K_x}

另外对于 t\in T，f_{T,t}=k_t=b_t=0。由此容易从下往上 DP 一遍求出 f_{T,x} 的值。

那么现在我们已经能够枚举子集以 O\!\left(Qn2^n\right) 的复杂度解决此题了。事实上因为 n 远小于 Q，所以预处理所有 S 的 f_{S,x_0} 可以做到 O(Q2^n)。

而事实上对于每个询问，我们求的是这个东西：

\text{Ans}_S=\sum_{T\subseteq S}\alpha_{|T|}f_{T,x_0}

则预处理后直接 FWT/FMT/高维前缀和能在 O(n2^n) 时间复杂度内完成。

void dfs(ll x,ll fa,ll S){
    if((1<<x-1)&S)return;
    ll kn=0,bn=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa)continue;
        dfs(y,x,S),kn=(kn+K[y])%mod,bn=(bn+B[y])%mod;
    }
    kn=(deg[x]-kn+mod)%mod,kn=Qpow(kn,mod-2),
    bn=(deg[x]+bn)%mod,bn=bn*kn%mod,K[x]=kn,B[x]=bn;
}

P3251 [JLOI2012] 时间流逝

设当前还存在的能量圈的集合为 S，P 为上一个集合，\operatorname{suc}S 为其可转移得到的可重集合族，有转移：

f_S=1+f_{p(S)}+\frac{1-p}{|\operatorname{suc}S|}\sum_{K\in\operatorname{suc}S}f_K

边界是 S 中元素的和大于了 T。注意到 |\operatorname{suc}S| 仅与当前集合的最小元有关，一个集合是否为边界也仅与 S 中元素的和有关。也就是说，对于元素和 s、最小元 m 相同的两个集合 S_1,S_2，它们的转移行为是完全相同的。因此我们可以将这些集合记录为一整个集合族，而 (s,m) 唯一确定之。于是我们将信息 (s,m) 作为状态进行 DP。

一些其他的练习题

P6835 [Cnoi2020]线形生物
CF802L Send the Fool Further! (hard)