我讨厌 DP 和 COUNT 的100个理由（下）

51 【MX-S12-T4】Sea, you again

还是来做点抑郁症数位 DP 吧。

先考虑一个 \(f_B(x)\) 怎么算。显然，从低位往高位合并，如果当前段的和 \(\geq B\) 了，那么就新开一段。

据此，我们设计一个从低位往高位填的数位 DP。设已经填到从低往高第 \(i\) 位，当前这一段的和是 \(S\)，后面有 \(j\) 段时的方案数，转移直接记忆化搜索转移，可以做到 \(O(B^2 {n_R}^2)\)，拼一拼可以拿 \(50\text{pts}\) 左右。

发现后面有多少段是可以不要的，转移时新开段就乘 \(10\) 就行了。可以做到 \(O(B^2 n_R)\)。不过好像能拿的分差不多。

嗯嗯？不对啊。乘 \(10\) 的方向和填数的方向是不是反的？如果直接做的话前缀和优化就可以做到 \(O(B n_R)\)，但是有这个问题的话怎么办？这说明我没有理解数位 DP 的本质。还是看题解吧。

不行的原因有两个，一是因为进制不是 \(10\) 是 \(B\)（我谔谔），二是因为方向确实是反的。不过发现我们可以记录所有方案的 \(B^k\) 的和！这是一个新技巧，虽然也很典了。

写出来发现是个前缀和优化，直接做一做就行了。题解说比较 dirty work。所以还是先做杂题吧。

52 Nested Segments

先考虑没有 \(m\) 的限制时答案是什么。因为区间两两不交或包含，所以它会形成一个天然的分治结构。设 \(f(n)\) 表示无限制时所有区间属于 \([1,n]\) 时的选择方案数，枚举断点可以得到一个酷炫的自卷积形式即 \(f(n)=\sum\limits_{i=1}^{n-1}f(i)f(n-i)\)。然后 \(f(1)=1,f(2)=1,f(3)=2,f(4)=5,f(5)=14,\dots\)。很显然，这就是卡特兰数的自卷积形式，而 \(f\) 基本上就是卡特兰数。

有 \(m\) 也很简单。加上区间 \([1,n]\) 后对它给出的区间建棵树，然后答案就是若干个 \(f(x)\) 的乘积。原因显然。做完了。

53 电动力学

搞到圆方树上做。一旦确定了 \(S\) 集合对应的子连通块，我们可以确定其对应的 \((S,T)\) 二元组方案数为 \(2^{siz}2^{siz-\sum cnt_i}\prod (2^{cnt_i}-1)\)，其中 \(cnt_i\) 是每个叶子方点的叶子圆点个数。当对应的方点只有一个时需要特殊处理。