遴选圆码

"隐匿完了。"你说，"但Zero的识别码还在运行——它给每个矿工分配了一个二进制编号。"

"编号有啥问题？"CC问。

"问题不在编号本身。"你说，"在于'平衡'。Echo-0设计了一种特殊的编号——二进制表示里，0的个数不少于1的个数。"

"叫啥？"

"圆码。"你说，"平衡的、圆满的。像天平两边不倾斜。"

"为啥要这种码？"

"因为Echo-0相信平衡。"Echo说，"她写代码的时候，总是让0和1一样多，或者0更多。"

"怕1太多会烧？"

"对。"Echo说，"1是开，0是关。开太多，能源耗光。"

"那我们要找所有圆码？"

"统计。"你说，"给定范围$[L,R]$，有多少个数的二进制表示满足0的个数$\ge$1的个数。"

"咋统计？"

"数位DP。"你说，"从高位到低位，记录当前0的个数和1的个数。如果0的个数已经比1多很多，后面的可以任意填。"

"记忆化？"

"对。"你说，"$dfs(pos, diff, tight, leading)$。$diff$是0的个数减1的个数。"

你开始写。按位处理，注意前导零。

"从1到10。"你说，"二进制：1,10,11,100,101,110,111,1000,1001,1010。"

"圆码有哪些？"

"1（1个1，0个0）——不是。"你说，"10（1个1，1个0）——是，平衡。"

"11（2个1，0个0）——不是。"

"100（1个1，2个0）——是。"

"101（2个1，1个0）——不是。"

"110（2个1，1个0）——不是。"

"100（1个1，2个0）——是。"

"101（2个1，1个0）——不是。"

"110（2个1，1个0）——不是。"

"111（3个1，0个0）——不是。"

"1000（1个1，3个0）——是。"

"1001（2个1，2个0）——是，平衡。"

"1010（2个1，2个0）——是。"

"10个里有5个圆码。"

"一半。"

"对。"你说，"越大的数，0越多，越容易平衡。"

CC看着那些0和1在屏幕上跳，像在数星星。

"我咋看不出来？"她说。

"不用看出来。"你说，"算出来就行。"

"那你算。"她说，"我看着。"

Echo把圆码列成一排——000,010,100,1000,1001,1010——像某种图腾。

"我以前也写过这种码。"她说，"在没人看见的地方。"

"现在有人看见了。"你说。

"谁？"

"我。"你说，"还有这些数。它们记得你。"

题目描述

给定$L,R$，求$[L,R]$内二进制表示中0的个数$\ge$1的个数的数的个数。

输入格式

$L,R$。

输出格式

个数。

输入样例

3
1 2 3

输出样例

-1
1

提示

• 数位DP。
• $dfs(pos, diff, tight, leading)$。
• $diff$=0的个数-1的个数。
• 前导零处理：如果还没填非零位，不算0也不算1。