【专题】析合树计数
析合树
子段：连续子序列
非平凡子段：长度 \(\in [2, n - 1]\) 的子段
连续段：排序后值域连续的子段
令 \(I_U\) 表示 \(U\) 的所有连续段。
本原连续段：若没有其他 \(I_U\) 内的连续段与当前连续段相交，则当前连续段称作本原连续段。
用一个连续段 \(x\) 代表一个节点 \(u\)，将 \(x\) 分成若干个非自身本原连续段，记作 儿子段，对应 \(u\) 连向若干个子节点。
这些子节点都对应一段连续值域，按值域给子节点赋排名 \(p_i\)，被称为 儿子排列。
定义 \(x\) 的 完整子段 表示非自身、非其儿子段、完全包含某些儿子段（不会把儿子段分裂）的子段。
下面是对当前 \(x\) 的分类：
\(x\) 是 合点：\(p\) 是顺序或逆序，即 \(x\) 的任意完整子段都是连续段。
\(x\) 是 析点：即非合点，此时有 \(x\) 的任意完整子段都不是连续段。易知 析点的子节点数量至少为 \(4\)。
CF1089I Interval-Free Permutations
洛谷：CF1089I Interval-Free Permutations
Codeforces：CF1089I Interval-Free Permutations
Problem
给您一个模数 \(p\) 和 \(n\)，请您输出长度为 \(n\) 同时不包含非平凡连续段的排列方案总数。\(n \le 400, T \le 400\)。
Solution
析合树计数：
- 根为析点
- 根的儿子均为叶节点，即 \(n\) 个叶节点
记 \(f_n\) 表示长为 \(n\) 的排列的答案。
正难则反，\(f_n = n! - 根为合点的数量 - 根为析点且其儿子数 \in [4, n - 1] 的数量\)。
-
根为合点
先假设儿子排列为顺序，逆序情况与顺序方案数相同。
枚举第一个儿子的值域范围为 \([1, i]\)，统计这样的儿子数量，记为 \(g_i\)。
由本原连续段的限制，该儿子首先得是包含 \(1, 2, \cdots, i\) 各一次的连续段，其次其任意长为 \(j(0 < j < i)\) 的前缀不能填满值域 \([1, j]\)。
容斥，
\[g_n = n! - \sum\limits_{i = 1}^{n - 1}g_i(n - i)! \]根为合点的总方案数为：
\[2\sum\limits_{i = 1}^{n - 1}g_i(n - i)! \] -
根为析点且其儿子数 \(\in [4, n - 1]\)
枚举儿子数 \(i\)，把 \(n\) 个节点分配到 \(i\) 个儿子中后再乘 \(f_i\)。
设 \(h_{i, j}\) 表示把 \(j\) 个节点分配到 \(i\) 个儿子中的方案数。小毬放盒问题，盒无编号，小毬在盒内要排序。
\[h_{i, j} = \sum\limits_{k = 1}^{j}h_{i - 1, j - k}\times k! \]则该情况的方案数为
\[\sum\limits_{i = 4}^{n - 1}h_{n, i}\times f_i \]上式是因为不论是单个节点还是打包成盒子，其本质都是儿子排列，所以可以直接把之前的 \(f_i\) 拖过来算。
\(O(n^3)\)。
code CF1089I Interval-Free Permutations
LOJ6632 Mysterious … Host
Problem
求本质不同的 \(n\) 阶析合树数量。\(n \le 5000\)。
本质不同即为在原排列上存在一段区间使得二者一个连续，一个不连续。
Solution
记 \(f_n\) 为本质不同的 \(n\) 阶析合树数量。
记 \(g_{n, i}\) 表示把长为 \(n\) 的排列分成 \(i\) 个连续段的本质不同的析合树数量。
\[g_{n, i} = \sum\limits_{j = 1}^{n}g_{n - j, i - 1}\times f_{j} \]（看了好一会儿最后一项...其实最后一项没有用的）
转移时，要对当前根节点为合点还是析点进行分类讨论，因为二者对应的若干完整子段连续性相反。
若为合点，需满足儿子数量至少为 \(2\)，贡献 \(\sum\limits_{i = 2}^{n}g_{n, i}\)。
若为析点，需满足儿子数量至少为 \(4\)，贡献 \(\sum\limits_{i = 4}^{n}g_{n, i}\)。
不论是合点还是析点，都可以有安排值域的方法取遍上述和式的所有情况。
即
\[f_n = \sum\limits_{i = 2}^{n}g_{n, i} + \sum\limits_{i = 4}^{n}g_{n, i} \]直接转移的时间复杂度是 \(O(n^3)\) 的。发现两部分非常相似，不妨设 \(h_{n} = \sum\limits_{i = 2}^{n}g_{n, i}\)，则
\[f_{n} = 2h_{n} - g_{n, 2} - g_{n, 3} \]这样就没必要 \(O(n^3)\) 求出 \(g\) 的所有值了，只需要求出 \(h_{n}, g_{n, 2}, g_{n, 3}\) 即可。其中 \(h_{n}\) 将 \(g_{n, i}\) 的式子代入即可得到递推式：
\[h_n = \sum\limits_{i = 1}^{n - 1}f_{n - i}(h_i + f_i) \]转移的时候注意 \(g_{n, 1}\) 就是 \(f_{n}\)。
code LOJ6632 Mysterious … Host
标签：专题,limits,sum,儿子,计数,连续,析合树,节点 From： https://www.cnblogs.com/Schucking-Sattin/p/17499206.html