A - 数一数
总感觉是做过的题，甚至清晰的记得给赵爷讲过，但是想不起来做法了…… :sob:
ZJK 告诉我题意是有问题的，每一列只能有恰好一个 $1$ ，否则样例 1 的答案就应该是 $\frac{3}{4}$ 。
整个表格的数确定的时候，用一个简单的 dp（$g_{j,i} = \max\{ g_{j+1,i-1}, g_{j+1,i}, g_{j+1,i+1}\} + v_{j,i}$）就能得到这个表格的最大得分。可惜由于表格无限长，这个 dp 的可能的取值也是无限多的，不能作为 dp 状态。
不妨设 $g’_{j,i} = g_{j,i} - \min_{k\in [1,n]} \{ g_{j,k} \}$ ，不难发现 $g’_j$ 的取值是有限的，并且将 $g_j$ 替换成 $g’_j$ 并不会影响之后的转移。
考虑这样一张图：每个结点是一个 $g’_j$ ；有向边 $(u,v)$ 的权值为二元组 $(p,w)$ ，表示当前在 $u$ ，下一步走到 $v$ 的概率是 $p$ ，而 $v$ 的 $\min\{g’_{j,k}\}$ 比 $u$ 大 $w$ 。设在这张图上随机游走 $m$ 步之后，走过的边的 $w$ 的和的期望为 $f(m)$ ，答案就是 $\lim_{m\to \infty} \frac{f(m)}{m}$ 。
$\lim_{m\to \infty} \frac{f(m)}{m}$ 等价于每条边的权值按照其被经过的期望次数加权平均，用高斯消元算即可。
B - 数二数
对于一个序列和一个询问集合，设 $S_i$ 为包含了 $i$ 这个位置的询问的集合。一个询问集合合法当且仅当 $S_i$ 互不相同。
性质 1 ：如果 $a<b<c<d, S_a=S_c, S_b=S_d$，那么 $S_a=S_b=S_c=S_d$ 。
证明：包含了 $a$ 和 $c$ 的询问必然包含 $b$ ，而由于 $S_b=S_d$ ，所以也就必然包含了 $d$ 。其它情况同理。
性质 2 ：假设 $a$ 是序列中第一个其 $S_i$ 至少出现了两次的元素，$b$ 是 $S_a$ 最后一次出现的位置，那么询问集合中不存在区间与 $[a,b]$ 有交且不互相包含。
证明：对于一个与 $[a,b]$ 相交且不互相包含的区间，这个区间必然只包含了 $a,b$ 中的一个，于是推出 $S_a\neq S_b$ ，矛盾。
统计不合法的询问集合数量。对于一不合法的询问集合和一个序列，我们对 $\{S_i\}$ 进行如下的操作：
- 找到第一个出现了至少两次的 $S_i$ ，然后找到它最后一次出现的位置，设这两个位置是 $l,r$
- 将 $[l,r]$ 区间内的元素删掉，替换为一个 $S_i = S_l$ 的元素，并重复 1.
显然不会有与被删掉的区间有交但不包含的询问；所以确定“没有被包含于删掉了的区间的询问”的方案数就是把被删掉的区间换成一个点之后的合法的询问集合数；被包含在删除了的区间内部的询问可以任意地确定。
设表示 $f_i$ 序列长度为 $i$ 时，合法的询问集合的数量；设 $s_{i,j}$ 表示有 $i$ 个被删除的区间，其总长度为 $j$ ，确定被这些区间完全包含了的询问的方案数。计算 $f_i$ 的时候枚举被删掉的区间数量和长度总和即可。