1680-连接连续二进制数字

给你一个整数 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

方法一：模拟

思路与算法

由于我们需要将「十进制转换成二进制」「进行运算」「将结果转换回十进制」这三个步骤，因此我们不妨直接将整个问题在十进制的角度下进行考虑。

假设我们当前处理到了数字 i，并且前面 [1, i-1] 的二进制连接起来对应的十进制数为 x，那么我们如何将数字 i 进行连接呢？

观察二进制连接的过程，我们可以将这一步运算抽象为两个步骤：

• 第一步会将之前 [1, i-1] 的二进制数左移若干位，这个位数就是 i 的二进制表示的位数；

• 第二步将 i 通过加法运算与左移的结果进行相加。

将上面所有的运算转换为 10 进制，我们就可以得到 x 的递推式，即：

x = x \cdot 2^{\textit{len}_2(i)} + i

其中 len}_2(i) 就表示 i 的二进制表示的位数，它可以通过很多语言自带的 API 很方便地计算出来。但我们还可以想一想如何通过简单的位运算得到 len}_2(i)。

我们可以这样想：由于 len_2(i-1) 和 len_2(i) 要么相等，要么相差 1（在二进制数发生进位时），因此我们可以使用递推的方法，在枚举 i 进行上述运算的过程中，同时计算 len}_2(i)。如果 len_2(i-1) 和 len_2(i) 相差 1，那么说明 i 恰好是 2 的整数次幂，问题就变成了如何判断 i 是不是 2 的整数次幂，这就有两种常用的方法了：

• 第一种是找出一个比任何数都大的 2 的整数次幂，比如本题中由于 n \leq 10^5，因此我们可以使用 2^{17}=131072，那么只要 131072 % i = 0，那么 i 就是 2 的整数次幂。

• 第二种是使用位运算，由于 2 的整数次幂的二进制表示形如 (1)_2 或者 (10\cdots0)_2 的形式，将其减去 1 是形如 (0)_2 或者 (01\cdots1)_2 的形式，恰好就是将减去 1 之前的二进制表示翻转之后的结果，因此如果 i & (i-1) = 0，即 i 和 i-1 的二进制表示中没有某一位均为 1，那么 i 就是 2 的整数次幂。

通过上面的方法，我们就可以 O(1) 地计算出 len}_2(i) 了。

代码

[sol1-C++]

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int concatenatedBinary(int n) {
        // 
        int ans = 0;
        int shift = 0;
        for (int i = 1; i <= n; ++i) {
            // if (131072 % i == 0) {
            if (!(i & (i - 1))) {
                ++shift;
            }
            ans = ((static_cast<long long>(ans) << shift) + i) % mod;
        }
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        # ans 表示答案，shift 表示 len_{2}(i)
        ans = shift = 0
        for i in range(1, n + 1):
            # if 131072 % i == 0:
            if (i & (i - 1)) == 0:
                shift += 1
            ans = ((ans << shift) + i) % mod
        return ans

复杂度分析

• 时间复杂度：O(n)。

• 空间复杂度：O(1)。

方法二：数学

前言

看不懂也没关系。

思路与算法

设 [a-t, a] 的二进制表示的位数均为 k，那么这一部分的和就为：

S = a + (a - 1) 2^k + (a - 2) 2^{2k} + \cdots + (a-t) 2^{tk}

使用高中数学的数列差分求和知识可以解得：

S = \cfrac{\cfrac{2^k(2^{tk}-1)}{2^k-1} + (a-t) 2^{(t+1)k} - a}{2^k - 1}

由于 k 比较小而 a,t 比较大，因此我们可以用快速幂优化计算。令：

\begin{cases}
u = 2^{tk} \
v = (2^k-1)^{-1} \
w = 2^{(t+1)k} \
\end{cases}

其中 t^{-1 表示在 t 在模 10^9+7 意义下的乘法逆元。带入得：

S = \left(2^k(u-1)v + (a-t)w - a\right)v

在计算 S 的同时需要维护后缀 0 的个数。

代码

[sol2-Python3]

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

复杂度分析

• 时间复杂度：O(\log^2 n)。

• 空间复杂度：O(1)。