方法一：模拟

思路与算法

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

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

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

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

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

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

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

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

我们可以这样想：由于 $len_2(i-1)$ 和 $len_2(i)$ 要么相等，要么相差 $1$（在二进制数发生进位时），因此我们可以使用递推的方法，在枚举 $i$ 进行上述运算的过程中，同时计算 $\textit{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)$ 地计算出 $\textit{len}_2(i)$ 了。

代码

###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;
    }
};

###Python

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$ 的个数。

代码

###Python

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)$。