解题思路
每次操作可以选取两个已有的数字标记进行逻辑与,并将结果加入集合。由于新值可以反复参与运算,最终可达的任意标记,必然可以表示为初始标记的某个非空子集的按位与结果。因此,问题转化为:
在数值范围 [0,1023] 内,统计有多少个整数 mask 能够被表示为至少一个初始标记的非空子集的按位与。
可达判定方法
若一个 mask 可以由某个子集按位与得到,则该子集中的每个标记都必须包含 mask 的所有 1 位,即 (mark&mask)=mask。设 S(mask) 为所有满足此条件的初始标记的集合。如果 S(mask) 非空,并且 S(mask) 中所有元素的按位与结果恰好等于 mask,那么 mask 就是可达的。