题目内容

小红参加ACM竞赛的过程中遇到过各种各样的计数题。唯独二进制计数题他整不明白。这不，今天WZ银行恰好又出了一道这种题，他还是依旧大脑空白。你可以帮助他吗？

小红拿到了四个非负整数$L$,$R$,$X$,$Y$，请计算有多少个非负整数$N$满足以下四个条件：

题解：位运算+组合计数

首先，考虑$N\&X=X$，对于$X$二进制位中每一个为1的位置，$N$与其对应的位置也必须要为1，我们可以使用一个标记数组进行标记

其次，考虑$N|Y=Y$，对于$Y$二进制位中每一个为0的位置，$N$与其对应的位置也必须要为0，我们可以使用一个标记数组进行标记

无解情况：上述标记的数字出现了冲突，则一定无解：同一个位置不可能既填1又填0

那么我们可以考虑一下对于有解情况的方案数：假设现在已经填了$m$个数字，其中有$k$个1，我们最终填写1的个数范围为$[L,R]$