A7656. [ABC129E] Sum Equals Xor
编程题
普及+/提高
知识点
题目描述
给定一个正整数 $L$，以二进制形式表示。请计算满足以下条件的非负整数对 $(a, b)$ 的个数：
- $a + b \leq L$
- $a + b = a\ \text{XOR}\ b$
由于答案可能非常大，请输出对 $10^9 + 7$ 取模的结果。
XOR 的定义如下：
对于整数 $A, B$，它们的按位异或 $a\ \text{XOR}\ b$ 定义为：
将 $a\ \text{XOR}\ b$ 用二进制表示时，第 $2^k$ 位（$k \geq 0$）的值为：如果 $A, B$ 的二进制表示中第 $2^k$ 位只有一个为 $1$，则该位为 $1$，否则为 $0$。例如，$3\ \text{XOR}\ 5 = 6$（二进制为：$011\ \text{XOR}\ 101 = 110$）。
- $a + b \leq L$
- $a + b = a\ \text{XOR}\ b$
由于答案可能非常大，请输出对 $10^9 + 7$ 取模的结果。
XOR 的定义如下：
对于整数 $A, B$，它们的按位异或 $a\ \text{XOR}\ b$ 定义为：
将 $a\ \text{XOR}\ b$ 用二进制表示时，第 $2^k$ 位（$k \geq 0$）的值为：如果 $A, B$ 的二进制表示中第 $2^k$ 位只有一个为 $1$，则该位为 $1$，否则为 $0$。例如，$3\ \text{XOR}\ 5 = 6$（二进制为：$011\ \text{XOR}\ 101 = 110$）。
输入格式
输入以以下格式从标准输入读入。
> $L$
> $L$
输出格式
请输出满足条件的 $(a, b)$ 组数，对 $10^9 + 7$ 取模。
输入输出样例
输入 #1
10
输出 #1
5
输入 #2
1111111111111111111
输出 #2
162261460
说明/提示
### 限制
- $L$ 以二进制形式给出，首位一定是 $1$
- $1 \leq L < 2^{100001}$
### 样例解释 1
满足条件的 $(a, b)$ 有 $(0, 0),\ (0, 1),\ (1, 0),\ (0, 2),\ (2, 0)$ 共 $5$ 组。
- $L$ 以二进制形式给出，首位一定是 $1$
- $1 \leq L < 2^{100001}$
### 样例解释 1
满足条件的 $(a, b)$ 有 $(0, 0),\ (0, 1),\ (1, 0),\ (0, 2),\ (2, 0)$ 共 $5$ 组。