大小为 n 的二叉堆计数怎么做

hdkk @ 2025-01-10 19:32:51

by System__Error @ 2025-01-10 19:37:09

/bx/bx

by System__Error @ 2025-01-10 19:38:26

@hdkk 点权互不相同吗

by hdkk @ 2025-01-10 19:40:03

@System__Error 是的，忘说了

by System__Error @ 2025-01-10 19:44:41

@hdkk 是我理解错你的意思了吗？二叉堆是完全二叉树，形态确定了的话咋做都是线性的啊/yun

by misaka_sama @ 2025-01-10 19:47:24

@hdkk 分治 ntt？

by hdkk @ 2025-01-10 19:48:36

@System__Error 啊这我才知道，我好唐/kk，严谨地说应该是带权的二叉树，满足父亲节点权值小于儿子权值才对，并且权值是排列

by hdkk @ 2025-01-10 19:50:26

@misaka_sama 求细说

by misaka_sama @ 2025-01-10 19:55:08

@hdkk f_n 为 n 个节点的答案，那么 f_n=\sum_{i=1}^{n-2} \binom{n-1}{i}f_i \times f_{n-i-1} ，分治 ntt 做半在线卷积。

by misaka_sama @ 2025-01-10 19:55:48

@hdkk 欸不区分意思是最后除以 2 吗？

by hdkk @ 2025-01-10 20:02:04

@misaka_sama 是的，拜谢您了/bx/bx