专栏文章

草稿纸（这是真的）

DDE_aemmprty
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzsuz4
此快照首次捕获于
2025/12/01 18:14
3 个月前
此快照最后确认于
2025/12/01 18:14
3 个月前
查看原文

ZR3422

问题 1
给定两个排列 aa 和 bb，其中 aa 大小为 nn，bb 大小为 mm。
现在你需要对长度为 n+mn + m 的排列 cc 计数，要满足：
  • cc 的前 nn 项大小关系和 aa 相同
  • cc 的后 mm 项大小关系和 bb 相同
Sol 1
答案是 (n+mn)\binom{n + m}{n}。易证。
问题 2
给定两棵树 aa 和 bb，其中 aa 大小为 nn，bb 大小为 mm。
现在你需要对大小为 n+m+1n + m + 1 的树 cc 计数，要满足：
  • cc 的根节点是 11，且 11 有两个儿子。
  • cc 的左子树编号的大小关系和 aa 相同。
  • cc 的右子树编号的大小关系和 bb 相同。
Sol 2
答案是 (n+mn)\binom{n + m}{n}。其实和上一个一样。
问题 3
回到原题。
设 fu,xf_{u, x} 表示以 11 为根，大小为 uu，深度为 xx 的树。
转移是每次给这棵树加入一颗新的子树，假设新的子树大小为 pp，深度为 qq，则有转移：
fu,xfp,q(u+p−1p)→fu+p,max⁡{x,q}f_{u, x}f_{p, q}\binom{u + p - 1}{p} \to f_{u + p, \max\{x, q\}}
上面的转移有问题，问题在哪。
Sol 3
假设有两种子树，A,BA, B，我们加入子树的顺序可能是 ABAB，也可能是 BABA，会导致算重复。
问题 4
如何去重。
Sol 4
加条件。假设加入的子树是从 p1p_1 到 pkp_k 按顺序加入的，那么我们令这些子树的最大编号是递增的。
就是每次加入新的子树，我们强制令这个子树的最大编号是整棵树的最大编号。
新的转移式就是新家的子树少了一个点（最大编号那个点被固定了），因此是：
fu,xfp,q(u+p−2p−1)→fu+p,max⁡{x,q}f_{u, x}f_{p, q}\binom{u + p - 2}{p - 1} \to f_{u + p, \max\{x, q\}}。
问题 5
复杂度过大，考虑优化。
Sol 5
我们枚举 u,p,t=max⁡{x,q}u, p, t = \max\{x, q\}，那么就有：
fu+p,t=(∑x=0tfu,xfp,t+∑q=0t−1fu,tfp,q)(u+p−2p−1)f_{u + p, t} = (\sum_{x = 0}^{t}f_{u, x}f_{p, t} + \sum_{q = 0}^{t - 1}f_{u, t}f_{p, q})\binom{u + p - 2}{p - 1}
使用前缀和优化即可。
BONUS
其实上面的常数有点大（我过不了），因此有一种更牛的 DP。
我们将深度为 xx 的树的个数转化为深度 ≤x\leq x 的树的个数。
设 fu,xf_{u, x} 表示大小为 uu，根节点编号为 11，深度 ≤x\leq x 的树的个数。
这样的好处是拼上一个子树可以直接使用 fp,x−1f_{p, x - 1}，不用前缀和优化。还算简单，自己研究。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...