考虑对于一个固定的 kkk 怎么 O(2n)O(2^n)O(2n) 求出答案。
先建出 Trie,令 ppp 为当前所在结点,vvv 为当前的答案。从高往低遍历 kkk 的每一位,每次可以将 ppp 移动到左儿子或右儿子;在 kkk 当前位为 000 是 vvv 加上没有移动到的儿子的子树和。最后 ppp 移动到叶子结点时 vvv 加上当前点的 aaa。显然每个结点只会被 dfs 到一次。
考虑将这个过程倒过来 dp。注意到在一个结点处的状态只有子树大小种,所以我们每次合并左右儿子的 dp 数组就可以了。
复杂度 O(n2n)O(n2^n)O(n2n)。
使用您的 Hydro 通用账户