DP 超大杯训练

树的拓扑序计数

\[\begin{align} f_u &= \binom{sz_u - 1}{sz_{v_1}, sz_{v_2}, \cdots, sz_{v_k}}\prod_{v \in son(u)}f_v \\ &= \frac{(sz_u - 1)!}{\prod_{v \in son(u)} sz_v!} \prod_{v \in son(u)} f_v \end{align} \]

将 \((sz_u - 1)!\) 看作 \(\frac{sz_u!}{sz_u}\) 就会发现全消掉了。剩下：

\[f_u = \frac{sz_u!}{\prod_{v \in \operatorname{subtree}(u)} sz_v} \]

CF1842G

这我不是做过。

先把期望变成总和除以方案数的形式，于是变成了计数题。

不难发现可以将类似 \(\prod (a_i + v + \cdots)\) 的式子拆开，相当于每个多项式中选一项，对这个东西计数。

设 \(f_{i, j}\) 表示前缀 \(i\) 钦定了 \(j\) 个操作。那么转移分为当前 \(i\) 用 \(a_i\)，或之前就钦定过的 \(v\)，或者我们新钦定一个 \(v\)。

有 \(f_{i + 1, j} \leftarrow f_{i, j}(a_{i + 1} + jv)\)，\(f_{i + 1, j + 1} \leftarrow f_{i, j}(m - j)(i + 1)v\)。

然后计算答案的时候考虑我们一个 \(f_{n, i}\) 还剩下 \(n - i\) 个操作没有钦定，并且这 \(n - i\) 个操作我们没有算它的贡献。

于是答案就是 \(\frac{\sum f_{n, i}n^{m - i}}{n ^ m}\)。

Submission #346781781 - Codeforces

AGC022E

好牛的题，考虑判定转 DP。

考虑建一个 DFA 出来。如果 000 直接删掉，而 111 显然可以保留到最后，剩下的情况等价于相邻 01 对消。

那么判定一个串是否合法开一个栈即可，前半部分全是 1 后半部分全是 0，如果新加入 1 就和 0 消除，新加入超过三个 0 就消成一个。

容易发现此时只要有两个 1 就一定赢了，因为 0 也不超过两个。按照这个过程 DP 即可。

uoj748

考虑判定 \(S\) 能否到 \(T\)，一个假的贪心是直接将 \(S\) 不断地匹配到 \(T\)，但者会被 S = (((( T=()()(((( 卡掉。

考虑反悔贪心那就是对的了，于是 DP 设 \(f_{i, j, k}\) 表示 \(T\) 匹配到 \(i\)，\(S\) 匹配到 \(j\)，当前 \(T\) 中未匹配部分的前缀和为 \(k\)。如果出现 \(k < 0\) 的情况就直接反悔即可。

P9197

做过，非常典的连续段 DP。从小到大插入维护连续段即可。

AGC060C

好牛的题。

会发现题目给出一个满二叉树 \(u\) 和 \(v\) 一个在极左链上一个在极右链上，我们考虑从小到大填数，那么会发现填数的过程相当于树的拓扑序。

于是只有 \(u\) 和 \(v\) 到根的两个链是有用的，记 \(f_{i, j}\) 表示处理了左链的前 \(i\) 个结点，右链的前 \(j\) 个结点， \(P_u < P_v\) 的概率。

假设要将 \(i + 1\) 放入新的拓扑序里，那么要乘上 \(\frac{\binom{x + y}{x}}{\binom{x + y - 1}{x - 1}}\) 的概率，即 \(\frac{x}{x + y}\)。

qoj8047

很难很难。

先将 dfs 序对应到唯一的一棵树上。会发现有的东西在字数内和作为兄弟是一样的，于是我们钦定以下大小关系：父亲小于儿子，兄弟之间顺序排列，最后一个儿子大于兄弟。小于是连边的方向。

考虑将儿子到兄弟的边容斥掉，算不存在这条边的方案减去反边的方案，具体画个图就知道了。

计数考虑 DP 设 \(f_{i, j}\) 表示子树大小为 \(i\)，且兄弟连出去的部分大小为 \(j\)。转移也很复杂，自己推一推吧。

qoj1839

显然将 \(p,q\) 交换使得 \(p_i = i\) 并没有影响。

不难刻画出判定条件为不存在一对 \((i, j)\) 使得 \(i < j, q_i > q_j, s_i = 1, s_j = 0\)。

将 \((i, q_i)\) 拍进坐标系里，相当于要存在一条折线将坐标系分成两半，左上角都是 \(0\)，右下角都是 \(1\)。

结论：如果 \(q\) 确定，那么合法 \(s\) 的数量是 \(q\) 的上升子序列的数量。

那么我们直接对可能的上升子序列计数。记 \(f_{i, j, k}\) 表示前 \(i\) 个位置，当前子序列末尾为 \(j\)，当前有 \(k\) 个位置没有填数。

最终答案为：\(\sum f_{n, j, k} \cdot k!\)。

AGC020F

好诡异的套路。

先破环为链，会发现线段的长度为整数，于是我们只关心整数部分的数值和小数部分的相对大小。

那么我们可以直接 \(O(n!)\) 枚举小数部分的相对大小，相当于离散化。然后 DP 设 \(f_{i, j, s}\) 表示当前处理完了坐标 \(\leq i\) 的线段，向右延伸到了 \(j\)，用的线段状态为 \(s\)。

于是我们用神秘 \(O(n!2^n(nc)^2)\) 完成了这道题。

P4516

弱智题，设 \(f_{u, i, 0/1,0/1}\) 表示 \(u\) 子树内放了 \(i\) 个监听器，\(u\) 上是否放了监听器，\(u\) 是否被监听。

*P10064

只需要考虑叶子，令 \(S_u\) 为叶子 \(u\) 在新图上一步能到达的结点，显然 \(S\) 的并为一个连通块。于是我们将问题转化为连通块计数。

对连通块计数考虑点边容斥，每个点属于 \(S\) 的交的方案数减去边即可。

具体细节有点复杂，后面再补。

CF1476F

不算太难，考虑设 \(f_i\) 表示前 \(i\) 个灯笼覆盖到的最远前缀。

若第 \(i\) 个灯笼向右，则当 \(f_{i - 1} \geq i\) 时 \(f_i = \max(f_{i - 1}, i + p_i)\)；当 \(f_{i - 1} < i\) 时 \(f_i = f_{i - 1}\)。

若第 \(i\) 个灯笼向左，先找出最小的 \(f_t \geq i - p_i\)。那么 \(f_i \leftarrow \underset{t + 1\leq k \leq i}{\max}\{k + p_k\}\)。

第二种情况先二分 \(t\) 然后数据结构优化 \(k + p_k\) 的最大值即可。

qoj1355

设 \(f_{i, j}\) 为前 \(i\) 个音符错过了 \(j\) 个，且第 \(i\) 个音符错过的方案数。令 \(w_{l, r}\) 为 \(l \sim r\) 的所有音符都得到的贡献。

有 \(f_{i, j} = \max\{f_{i - 1, j - 1},\underset{k < i - 1}{\max}\{f_{k, j - 1} + w_{k + 1, i - 1}\} \}\)。

容易证明 \(w\) 满足四边形不等式，那么我们将 dp 视为从 \(f_{j - 1}\) 转移到 \(f_j\)，根据四边形不等式的结论：\(P_{j - 1, i - 1} \leq P_{j - 1, i}\)。

转移的时候直接分治即可优化到 \(O(n^2\log n)\)。

CF1988F

推式子基本功不够良好。

排列前缀最大值考虑一下连续段 DP，令 \(f_{i, j, k}\) 表示 \(i\) 个数的排列，前缀最大值有 \(j\) 个，有 \(k\) 个上升点，\(g_{i, j, k}\) 同理为后缀最大值。

记 \(S(n)\) 为长为 \(n\) 的排列的答案，那么枚举 \(n\) 的位置有

\[S(n) = \sum_{p = 1}^{n}\sum_{i, x = 0}^{p - 1}\sum_{j, y = 0}^{n - p} \binom{n - 1}{p - 1}f_{p - 1, i, x}g_{n - p, j, y}a_{i + 1}b_{j + 1}c_{x + y + [p > 1]} \]

记

\[A(n, x) = \sum_{i = 0}^n f_{n, i, x}a_{i + 1} \\ B(n, x) = \sum_{i = 0}^n g_{n, i, x}b_{j + 1} \]

则

\[S(n) = (n - 1)!\sum_{p = 1}^n \sum_{x = 0}^{p - 1}\sum_{y = 0}^{n - p} \frac{A(p - 1, x)}{(p - 1)!} \frac{B(n - p, y)}{(n - p)!}c_{x + y + [p > 1]} \]

由于要枚举 \(n\) 于是做到 \(O(n^4)\)。原因是每个 \(n\) 都单独算一遍比较蠢。

进一步令 \(S'(n) = \frac{S(n)}{(n - 1)!}\)，\(A'(n, x) = \frac{A(n, x)}{n!}\)，\(B'(n, x) = \frac{B(n, x)}{n!}\)，\(i = p - 1, j = n - p\)，我们枚举 \((i, j)\) 贡献 \(S(i + j + 1)\)。

\[S'(i + j + 1) \leftarrow \sum_{x = 0}^{i}A'(i, x)\sum_{y = 0}^j B'(j, y)c_{x + y + [i > 0]} \]

对每个 \(s_{i, x} = \sum_{y = 0}^j B'(j, y)c_{x + y + [i > 0]}\) 预处理即可做到 \(O(n^3)\)。

P11714

DAG 容斥模板题。

设 \(F_S\) 为将 \(S\) 中的点强连通的方案数，\(G_S\) 为 \(S\) 内的点缩成若干个入度为 \(0\) 的点的方案数，\(E_{S, T}\) 为 \(S\) 到 \(T\) 的边数。

有 \(F_S = 2^{E_{S, S}} - \sum_{T \subseteq S, T \not = \varnothing}(-1)^{?}G_T2^{E_{T, S - T} + E_{S - T, S - T}}\)。

? 处应该是缩成点的数量，但是我们并不知道这个，所以考虑把容斥系数直接计入 \(G\)，令 \(G_{S}\) 为 \(S\) 内的点缩成奇数个点（入度为 \(0\)）的方案数减去偶数个点的方案数。

此时 \(F_S = 2^{E_{S, S}} - \sum_{T \subseteq S, T \not = \varnothing}G_T2^{E_{T, S - T} + E_{S - T, S - T}}\)。

考虑如何转移 \(G\)，会发现缩点后的几个 SCC 之间没有关系，于是考虑钦定 \(\operatorname{lowbit}(S)\) 所属的 SCC 为最新加入的。

\(G_S = F_S - \sum_{T \subset S, \operatorname{lowbit}(S) = \operatorname{lowbit}(T)} F_TG_{S - T}\)。

注意这里的转移顺序一定是先算 \(G_S\) 不加 \(F_S\)，再算 \(F_S\)，再把 \(F_S\) 加到 \(G_S\) 上。

最后考虑怎么算 \(E_{S, T}\) 会发现用到的形式只有 \(E_{T, S - T}\) 和 \(E_{S, S}\)，后者单独算，前者每枚举一个 \(S\) 就算一个即可。

具体有：

\(E_{T, S-T} = E_{T + x, S - T - x} - \operatorname{popcount}(out_x \cap (S - T)) + \operatorname{popcount}(in_x \cap T)\)，

\(E_{S, S} = E_{s - x, s - x} + \operatorname{popcount}(in_x \cap S) + \operatorname{popcount}(out_x \cap S)\)。

于是我们只需要 \(O(3^n)\) 就可以解决这个问题。

P5642

没来得及做。