1 条题解

  • 0
    @ 2026-11-15 21:49:35

    题目分析

    考虑对于一个固定的 kk 怎么 O(2n)O(2^n) 求出答案。

    先建出 Trie,令 pp 为当前所在结点,vv 为当前的答案。从高往低遍历 kk 的每一位,每次可以将 pp 移动到左儿子或右儿子;在 kk 当前位为 00 是 vv 加上没有移动到的儿子的子树和。最后 pp 移动到叶子结点时 vv 加上当前点的 aa。显然每个结点只会被 dfs 到一次。

    考虑将这个过程倒过来 dp。注意到在一个结点处的状态只有子树大小种,所以我们每次合并左右儿子的 dp 数组就可以了。

    复杂度 O(n2n)O(n2^n)。

    • 1

    信息

    ID
    216
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者