Day1 计数类dp 知识点 & 部分例题

概率与期望 dp

相当于计数、数方案数的 dp，其中概率就是 $\frac{合法方案数}{总方案数}$。

• 直接想 dp 不正确，如在统计合法方案时先想想如何判合法。

Leftmost Ball

给出 $n$ 种不包含白颜色的不同颜色的球，每种颜色有 $k$ 个球，所有球除颜色外完全相同，将这些球摆成长 $nk$ 的一列，然后将每种颜色的球中最靠前的那个球染成白色。求可能的序列总数。$n\le 2000$。

显然我们只关心白球和第一个非白球的不同颜色的球，而对于后者与其相同颜色的球的贡献直接组合数算即可，不对答案造成影响。而对于最终的序列合法，当且仅当一共 $k$ 个白球和 $n$ 个颜色的球各有 $k-1$ 个，且对于任意的 $i$，在 $[1,i]$ 中白球数量不小于其他颜色的球的颜色种数。

考虑 dp，令 $f(i,j)$ 表示放了 $i$ 个白球 $j$ 种其他颜色的球的合法方案数，其中 $i,j$ 满足 $i\ge j$。转移时为了不重考虑序列中最靠左的空位上进行放置球。每当我们放置一种新的颜色的球时，就把所有的 $k-1$ 个同色的球的贡献一起计算掉。

• 如果放一个白球，则有 $f(i,j)\leftarrow f(i,j)+f(i-1,j)$，显然正确；
• 如果放一种新颜色的球（一起放完），则有

$$f(i,j)\leftarrow f(i,j)+f(i,j-1)\times (n-j+1)\times \left(\genfrac{}{}{0ex}{}{nk-i-(j-1)(k-1)-1}{k-2}\right)$$

• 其中，$n-j+1$ 表示剩余颜色种数，组合数表示从剩下的空位中选出 $k-2$ 个填上除了第一个球以外的同色球的方案数。由于每种颜色都有 $k-1$ 个且每次总是一起放完，所以可以直接得到空位数量。

Game with Marbles

袋子里有 $r$ 个红球、$g$ 个绿球和 $b$ 个蓝球，若干轮从袋子中等概率随机取出一个球，如果是红球就扔掉，如果是蓝球或绿球就放回去，求摸出第 $k$ 次蓝球时摸球次数的期望值。$r,g,b,k\le 10^9$。

显然最终次数的期望值可以由三种颜色的球分别被取出次数的期望值组合而成，考虑不断拆贡献。显然蓝球的贡献是 $k$。注意到绿球被取出时，既不会导致红球减少，也不会导致蓝球多模一个，所以我们先无视它们。

对于红球，我们单独考虑每一个红球，假设袋子中只有这一个红球和 $b$ 个蓝球。那么它单轮不被取出的概率就是 $\frac{b}{b+1}$，取 $k$ 次蓝球下来，这个红球被取出的概率即为 $1-{\left(\frac{b}{b+1}\right)}^k$。推广到 $r$ 个红球，总贡献即为 $(\frac{1}{b+1})\times r$。

然后考虑绿球，注意到绿球基本和蓝球等价，所以通过直觉可以得到 $g$ 个绿球的贡献即为 $k\times \frac{g}{b}$。这一步有严谨证明但是我没记住也不会。最终答案三者相加即可。

Fortune Wheel

给定一个长度为 $n$ 的环，钦定一个起点 $x$，共 $k+1$ 种操作，前 $k$ 种操作给出一个长度为 $k$ 的数组 $P$，第 $i$ 种操作为：从当前位置顺时针移动 $P_i$ 个单位长度。第 $k+1$ 种操作为：等概率随机一个环上的位置，然后跳到那个位置。求最优策略下从起点出发到达点 $1$ 的期望操作数。

显然随机操作可以放到一开始还没有进行常规移动进行，且进行随机操作的意义显然是跳到一个最短路更短的一个或一些点上。那么我们先 bfs 计算出每个点到起点的最短路，然后考虑什么时候随机什么时候直接走。

我们把每个点的最短路从小到大排序，枚举这个随机与直接走的阈值 $w$；如果从起点出发的最短路大于 $w$，就进行若干次随机，随机到一个最短路在 $w$ 之下的点。设当前枚举到第 $i$ 个点的最短路作为 $w$，那么随机到 $[1,i]$ 中某个点的期望次数是 $\frac{n}{i}$；而随机完后显然走的期望最短路，就是 $[1,i]$ 中点的平均最短路。

青鱼和怪兽

初始玩家有 $n$ hp，怪兽有 $m$ hp，任意时刻玩家可以选择以下操作之一：

• 消耗 $1$ 单位时间，有 $p$ 概率怪兽 hp 减一，$(1-p)$ 概率玩家 hp 建议。
• 玩家 hp 和怪兽 hp 重置为 $n$ 和 $m$，不消耗时间。当玩家 hp 归零时强制触发重开操作。

求最优策略下期望经过多少单位时间把怪兽 hp 打空。期望与 $10^9$ 取 $\min$。

令 $f(i,j)$ 表示怪兽 $i$ hp、玩家 $j$ hp 期望操作值，因为涉及到重开所以式子长这样：
$$f(i,j)\leftarrow \min (f(n,m),p\times f(i-1,j)+(1-p)\times f(i,j-1))$$
很显然这个 dp 没法做，要算这个东西需要知道 $f(n,m)$，但是知道 $f(n,m)$ 需要算这个东西。所以我们考虑设定一个 $w$ 代替 $f(n,m)$ 放进转移方程中，然后与算出的 $f(n,m)$ 进行比较。显然最终算出的 $f(n,m)\le w$。

• 如果 $f(n,m)<w$，说明 $w$ 较大；
• 如果 $f(n,m)=w$，说明取 $\min$ 时总是选择往 $w$ 取，说明最终答案 $f_{\text{ans}}(n,m)$ 不大于 $w$。

然后我们发现，这个东西有单调性，于是考虑二分然后 $O(nm)$ 进行 dp 即可。

New Year and Arbitrary Arrangement

一个字符串初始为空，每一次有 $A=\frac{pa}{pa+pb}$ 的概率在末尾增加一个字符 $\text{a}$，有 $B=(1-A)=\frac{pb}{pa+pb}$ 的概率在末尾增加一个字符 $\text{b}$。当出现了至少 $k$ 个形如 $\text{ab}$ 的子序列（即不必连续）时停止。求 $\text{ab}$​ 子序列的期望数量。

考虑 dp。令 $f(i,j)$ 表示前缀中已有 $i$ 个 $\text{a}$ 和 $j$ 个 $\text{ab}$，停止后的期望数，那么转移方程即为
$$f(i,j)=A\times f(i+1,j)+B\times f(i,j+i)$$
其中，当 $i+j\ge k$ 时，往末尾多加一个 $b$ 就会停止。本来会由此得到一个无限求和式，但是通过变换可以得到，此时的期望值即为 $i+j+\frac{pa}{pb}$。这也是终止状态。由于在第一个 $\text{a}$ 出现前出现的 $\text{b}$ 不会对答案产生贡献，所以答案取 $f(1,0)$ 避免转移到自己。实现时可以使用记忆化搜索。

Strongly Connected Tournament

给出 $n$ 个点，对这 $n$ 个点生成一张竞赛图（即点两两连一条双向边），对于所有的 $i,j$（$i<j$），有 $p=\frac{a}{b}$ 的概率 $i$ 向 $j$ 连边，其余情况 $j$ 向 $i$ 连边。然后对图中的强连通分量缩点，对于每个强连通分量中的点也不断进行以上操作（随机生成竞赛图然后缩点），直到最终每个强连通分量只剩一个点。求所有操作中连的所有边的期望数量。

令 $f(i)$ 表示点数为 $i$ 时的图它的期望值。转移时，考虑枚举最弱的，也就是生成的竞赛图进行缩点后链的终点的那个强连通分量。这个最弱的 SCC，满足在 SCC 之外的所有点都向 SCC 内的每一个点连边，那么如果这个 SCC 大小为 $s$，算上它自己內部连的边，一共连了 $j\times (i-j)+\frac{j\times (j-1)}{2}$​ 条边。

进一步，我们需要计算这 $i$ 个点组成强连通图的概率 $g(i)$ 和其中 $j$ 个点被其他点全部打赢的概率 $h(i,j)$，其中显然满足 $j\le i$。反着想一下，只要图中没有点全输完了，即每个点都至少有一次打赢、出度至少为 $1$，此时这张图就是强连通的。于是有
$$g(i)=1-\sum _{j=1}^{i-1}g(j)\times h(i,j)$$
对于 $d$，每新加入一个点，它要么是输完了的 $j$ 个点中的一个被 $i-j$ 个点打赢，要么就得把 $j$ 个点全部打赢，于是有
$$h(i,j)=(1-p{)}^j\times h(i-1,j)+p^{i-j}\times h(i-1,j-1)$$
现在考虑 $f$ 的转移，容易得到
$$f(i)=\sum _{j=1}^{i}g(j)\times h(i,j)\times \left(j(i-j)+\frac{j(j-1)}{2}+f(j)+f(i-j)\right)$$
考虑当 $i=j$ 即整个图本身满足强连通时会从自己转移，于是进行变形，将此时的贡献单独拿出来即可。时间复杂度 $O(n^2)$。

BBQ Hard

给出两个长度为 $n$ 的数组 $a,b$，求
$$\left(\sum _{i=1}^n\sum _{j=i+1}^n\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)\right)\mathrm{mod}10^9+7$$
$n\le 2\times 10^5$，$1\le a_i,b_i\le 2\times 10^3$。

考虑 $\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)$ 的组合意义，可以转化为：在平面上从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$、只能向 $x$ 或 $y$ 轴正方向移动的走法方案数。但是这样终点的坐标与 $i,j$ 都有关，我们考虑平移，问题转变为从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数。然后就可以在坐标上进行 dp，记 $f(i,j)$ 表示走到 $(i,j)$ 的方案数，而起点就是所有的 $(-a_i,-b_i)$。最后记得删去 $i\ge j$ 时的重复贡献，用组合数计算即可。

MEX counting

• 重讲也不太会！（亢奋
• To be continued…

二项式反演

类似于容斥，抽象来说就是通过 $f_i$ 容易计算出 $g_i$，然后考虑从 $g_i$ 反推回 $f_i$。

min-max容斥

用子集的 $\min$ 和 $\max$ 推出集合的 $\min ,\max$ 甚至于第 $k$ 大，在算期望时也是正确的。

Beautiful Bracket Sequence (hard version)

给定一个由 $\text{(},\text{)},\text{?}$ 三种字符组成的字符串 $S$，其中 $\text{?}$ 可以变成左右括号中的任意一个。定义一个括号序列的权值为：对于它的所有一个合法的子字符序列，其括号匹配的层数的最大值。求所有方案下 $S$ 的权值和。

easy version:$n\le 2\times 10^3$；hard version:$n\le 10^6$​。

显然若钦定一个分界点 $i$，使得 $[1,i]$ 中的左括号数量等于 $[i+1,n]$ 中的右括号数量，那么此时就可以取到答案的深度等于 $[1,i]$ 中的左括号数量。我们考虑枚举这个分界点 $k$，然后记录 $[1,k]$ 中的左括号数量 $a_k$、$[k+1,n]$ 中的右括号数量 $b_k$ 和两侧的待定数量分别为 $c_k,d_k$，我们考虑枚举左侧有多少个 $\text{?}$ 变成左括号，则 $k$ 对答案的贡献即为
$$\sum _{i=0}^{c_k}(a_k+i)\times \left(\genfrac{}{}{0ex}{}{c_k}{i}\right)\times \left(\genfrac{}{}{0ex}{}{d_k}{a_k+i-b_k}\right)$$

这样 easy version 就做完了。考虑化简，得
$$\text{原式}=a_k\times \left(\genfrac{}{}{0ex}{}{c_k+d_k}{d_k-a_k+b_k}\right)+c_k\times \left(\genfrac{}{}{0ex}{}{c_k+d_k-1}{b_k+d_k-a_k-1}\right)$$

Merge Triplets

给定 $n$，求所有长度为 $3n$ 的排列 $A$，使得存在至少一个长度相同的排列 $B$，将 $B$ 每相邻 $3$ 个数分为一块，对这些块进行从小到大归并后能够得到 $A$。求方案数。

先考虑如何判断 $A$ 是否合法。在归并排序过程中，对于一个块 { a , b , c } \{a,b,c\} {a,b,c}，如果有 $a>b>c$，那么当 $a$ 被归并时 $b,c$ 一定紧接着被归并。其他情况是类似的。于是 $A$ 合法需要满足：按照前缀 $\max$ 所在的点进行划分，划分出的每一段长度都不超过 $3$。然后构造几组样例，可以得出另一个条件：划分出的段，长度为 $1$ 的段的个数不少于长度为 $2$ 的段。

于是我们考虑 dp。设 $f(i,j,k)$ 表示考虑了前 $i$ 个数，有 $j$ 个长度为 $1$ 的段，有 $k$ 个长度为 $2$ 的段。但是注意到我们只关心后两者之间的相对大小，于是状态可以简化为 $f(i,j)$，$j$ 表示 $1$ 段与 $2$ 段个数之差。转移时讨论划分的下一段的长度，乘上方案数即可。

Emiya 家今天的饭

给出一个 $n\times m$ 的表格，第 $i$ 行第 $j$ 列上有一个非负整数 $a_{i,j}$。需要在表格中选若干个位置，满足以下要求：

• 至少选取一个位置；
• 每行至多选一个位置；
• 设总共选了 $c$ 个位置，那么不存在一列选的个数超过 $\lfloor \frac{c}{2}\rfloor$​。

对于一种合法方案，它的权值是所有选的位置的 $a_{i,j}$ 的乘积。求所有合法方案的权值之和。

$n\le 100$，$m\le 2000$​。

注意到至多只会存在一列选择的位置超过 $\lfloor \frac{c}{2}\rfloor$。所以考虑容斥，用总权值和减去一列不合法的权值和即可。对于计算总方案数，我们记第 $i$ 行和为 $s(i)$，设 $g(i,j)$ 表示前 $i$ 行选了 $j$ 个数的权值和，则有
$$g(i,j)=g(i-1,j)+s(i)\times g(i-1,j-1)$$
然后考虑计算不合法方案数，我们枚举不合法的这一列（记为第 $k$ 列），然后类似的做一个 $O(n^2)$ 的 dp，令 $f(i,j)$ 表示前面 $i$ 行中，第 $k$ 列选的数比其他列多了 $j$ 个时的权值和，那么有
$$f(i,j)=f(i-1,j)+a_{i,k}\times f(i-1,j-1)+\left(s(i)-a_{i,k}\right)\times f(i-1,j+1)$$
实现时可以把第二维平移 $n$ 保证不越界。总时间复杂度 $O(n^{2}m)$。