考虑随机游走状的高斯消元:对于题目中的一个可重集 \(S\),令 \(f_S\) 表示,从 \(S\) 开始期望多少天后走到和 \(\ge m\) 的集合。
则有两种转移,分别对应摆烂或不摆烂:
(定义多重集减一个数为该集合去除一个该数,\(\min\{S\}\) 为多重集中最小元素,\(S \cup T\) 为两个多重集并)
\[f_S=p(1+f_{S-\min\{S\}})+\frac{1-p}{\min\{S\}}\sum_{i=1}^{\min\{S\}}(1+f_{S\cup \{i\}}) \]\[f_S=1+pf_{S-\min\{S\}}+\frac{1-p}{\min\{S\}}\sum_{i=1}^{\min\{S\}}f_{S\cup \{i\}} \]暴力可以依据这个式子高斯消元,可以求出每个 \(f\)。
考虑把状态之间的依赖关系画出来,容易发现这是一棵树,即 \(S-\min\{S\}\) 对应 \(S\) 在状态树上的父亲,\(S\cup \{i\}\) 对应它的每个儿子。
则即
\[f_u=1+pf_{fa_u}+\frac{1-p}{\min\{u\}}\sum_{v\in son_u}f_v \]此树的叶子即为和 \(\ge m\) 的状态。
如果状态数比较少,我们可以从叶子开始向上推出每个节点的 \(f\),但这里显然状态数很大很大。
注意到对于一个状态 \(S\),如果 \(S\) 的最小值、和是确定的,它的子树形态也是确定的。
那么将所有 \((\min,\text{sum})\) 相同的节点归为一个等价类,这样一共有 \(\Theta(nm)\) 个等价类。
但是一个等价类内的 \(f\) 是不一样的。我们发现一个等价类的儿子是确定的等价类(们),但是父亲是不确定的,因为不知道一个多重集去除最小值后最小值是否改变。
即便如此,观察 \(1\) 式,对于 \(\text{sum}\ge m\) 的等价类的节点,他们不存在儿子节点,因此 \(f_u=1+pf_{fa_u}\)。即 \(f_{fa_u}\) 和 \(f_u\) 间存在一次关系式。
归纳地,对于一般的节点 \(u\) ,若知道了 \(f_u\) 和每个儿子的 \(f_v\) 的一次关系式,我们可以将这个关系代入 \(1\) 式,消去所有和儿子有关的未知量,得到 \(f_{fa_u}\) 和 \(f_u\) 的一次关系式。
因此,对于同一等价类中的所有节点,他们的 \(f\) 和其父亲的 \(f\) 存在固定的一次关系。
若我们求出了每个等价类的这个一次关系,则由于询问的 \(S\) 到根的路径是可以求出的,我们由根的 \(f\) 递推到 \(S\) 的 \(f\) 就解决了此题。
求所有关系是相对容易的,对于状态 \((\min=x,sum=y)\),子状态形如 \((z,y+z)\),其中 \(1\le z\le x\)。
假设一次关系形如 \(f_{(x,y)}=k_{(x,y)}f_{fa_(x,y)}+b_{(x,y)}\),则要求的就是 \(\sum_{z=1}^xk_{(z,y+z)}\) 以及 \(\sum_{z=1}^xb_{(z,y+z)}\)。
前缀和优化即可,复杂度 \(\Theta(nm+q+\sum|S|)\)。
标签:reset,min,sum,cup,等价,fa,节点 From: https://www.cnblogs.com/iorit/p/18041623