难度: Medium
给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 7 取余的结果。
示例 1：
输入：n = 1 输出：1 解释：二进制的 "1" 对应着十进制的 1 。
示例 2：
输入：n = 3 输出：27 解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。 将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：
输入：n = 12 输出：505379714 解释：连接结果为 "1101110010111011110001001101010111100" 。 对应的十进制数字为 118505380540 。 对 109 + 7 取余后，结果为 505379714 。
提示：
1 <= n <= 105运行时间: 61 ms
内存: 16.1 MB
class Solution:
def concatenatedBinary(self, n: int) -> int:
mod = 10**9 + 7
zeroes = 0
ans = 0
for k in range(64, 1, -1): # 任意 64 位无符号整数都可以秒出答案
if (lb := 2 ** (k - 1)) <= n:
t = n - lb
u = pow(2, t * k, mod)
v = pow(2 ** k - 1, mod - 2, mod)
w = pow(2, (t + 1) * k, mod)
x = pow(2, zeroes, mod)
ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod
zeroes += (t + 1) * k
n = lb - 1
ans += pow(2, zeroes, mod)
return ans % mod
该题解采用了一种逆向思考的方法，通过逐步减小 n 的值来计算结果。算法从最大的可能的二进制位数开始，逐步向下计算。对于每个 k（从 64 到 2），检查 2^(k-1) 是否小于等于 n。如果是，则计算当前位数下的二进制数的贡献，并更新 n 和 zero 的值。最后，将所有贡献累加得到最终答案。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def concatenatedBinary(self, n: int) -> int:
mod = 10**9 + 7 # 定义模数
zeroes = 0 # 记录二进制串中 0 的数量
ans = 0 # 存储最终结果
for k in range(64, 1, -1): # 从最大可能的二进制位数开始逆向计算
if (lb := 2 ** (k - 1)) <= n:
t = n - lb
u = pow(2, t * k, mod)
v = pow(2 ** k - 1, mod - 2, mod)
w = pow(2, (t + 1) * k, mod)
x = pow(2, zeroes, mod)
ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod
zeroes += (t + 1) * k
n = lb - 1
ans += pow(2, zeroes, mod)
return ans % mod
逆向思考的方法允许从最大可能的二进制位数开始逐步向下计算，这样做可以更高效地利用二进制数的性质，减少重复计算。从1到n的顺序计算可能涉及到大量的字符串操作和位移，这在处理大量数据时会非常低效。逆向方法可以直接从较大的块开始处理，减少运算次数和提高效率。
`t` 表示从当前的二进制位数开始计数，直到n的剩余部分。`u` 是用于计算当前位数下所有可能的二进制数的和。`v` 是求模逆元，用于计算除法在模运算下的结果。`w` 用于调整计算结果，确保正确计算二进制数的总贡献。`x` 用于通过之前计算的0的数量来调整结果。这些变量相互作用，共同确定最终的模运算结果，确保在大数字计算中的正确性和效率。
使用pow函数进行幂运算和模运算非常高效，特别是在处理大数字时。Python的pow函数实现了模幂运算，这可以大幅减少计算时间和空间复杂度。特别是当基数和指数非常大时，直接计算将非常耗时和占用大量内存，而使用pow函数可以有效解决这个问题，确保算法在大规模输入下仍然高效。
`zeroes`变量记录的是在计算过程中，所有已处理的二进制数中0的总数量。这个数量对于调整每个新数值的位置非常重要，确保它们在最终结果中正确地拼接。例如，如果前面的数占据了多个二进制位，后续的数必须相应地左移这么多位，`zeroes`用于记录这个位移量。这确保了每个数的二进制表示在最终结果中的相对位置正确无误。