题解

思路推导

若一个数由另一个数经过操作得到，则可以按末尾二进制位逆推它的父结点：奇数只能由 $2y+1$ 得到，父结点为整除二后的值；能被 $4$ 整除的偶数可以由 $4y$ 得到，父结点为整除四后的值；模 $4$ 余 $2$ 的数没有父结点。

如果某个初始数沿这条唯一祖先链能够遇到另一个初始数，那么它及其全部后代早已由那个祖先生成，不应再次计数。依次检查每个初始数，可以筛出互不覆盖的根。

对一个二进制长度为 $l$ 的根，操作 $2y+1$ 会使长度增加 $1$，操作 $4y$ 会使长度增加 $2$。因此只需按二进制长度统计根的数量，再做一个由前一项和前两项转移的动态规划。

做法

把所有初始数放入集合。对每个初始数不断执行合法逆操作；若中途遇到集合中的另一个数，就把当前数判为冗余。对每个非冗余且二进制长度不超过 $p$ 的根，在对应长度上增加计数。

令 $dp_i$ 表示二进制长度恰为 $i$、且由保留根生成的数的数量。长度为 $i$ 的数可以是长度为 $i$ 的根，也可以由长度 $i-1$ 的数执行第一种操作得到，或由长度 $i-2$ 的数执行第二种操作得到。按长度递推并累加 $dp_1$ 到 $dp_p$ 即得答案。

正确性证明

每个可逆结点的父结点由最低二进制位唯一确定，所以沿祖先链检查不会遗漏任何可能生成该初始数的更早初始数。删去有初始祖先的数只会去除重复生成源，不会改变集合；保留的根之间不存在祖先关系，因此它们的后代集合互不相交。

对任一保留根，每次合法操作分别让二进制长度增加 $1$ 或 $2$，且两个操作产生的末尾二进制形态不同，不会把不同转移合并成同一个数。因此长度递推恰好计数所有且仅有长度不超过 $p$ 的后代。所有保留根的后代互不重叠，累加这些计数正好得到目标集合大小。

复杂度分析

每个初始数最多沿二进制长度逆推，时间复杂度为 $O(n\log A+p)$，其中 $A=\max a_i$；空间复杂度为 $O(n+p)$。