test20190816

点分治爆栈祭.

$phantasm$

将每次选择的位置看成一个数列,第一个位置必定是 $1$ ,所以只需要求出它的差分序列方案数.

差分序列中共 $m-1$ 个元素,每个元素必须 $\le k$ ,总和为 $n-1$ .

调整一下后用隔板法处理,答案是组合数,在模 $2$ 意义下,根据 $Lucas$ 定理,只需判断二进制位即可.

$skylines$

直接大力点分治预处理所有点的答案.

枚举子树时正反顺序都做一次,再考虑上分治中心.

时间复杂度 $O(n\log n+T)$ .

$kiseki$

题面写得太垃圾了.

每次从已有的数中选一个,得到它的权值,并获得它的后继,存档可以重复获得.

考虑 $dp$ ,状态只与当前有的存档集合有关,与顺序无关.

而从小到大排序后,相邻两项的差分值只可能是 $0/1$ ,所以可以用一个二进制数 $S$ 来记录.

设 $f(i,S)$ 表示有 $i$ 个存档,差分值的状态是 $S$ 的方案数,转移时枚举增加的存档.

总方案数是 $m!$ ,预处理差分状态 $S$ 对应的序列权值是 $val(S)$ ,答案就为

$$\sum_{S} \frac {f(m,S)} {m!} \cdot val(S)$$

时间复杂度 $O(m\cdot 2^m)$ .