题目

原题在此
Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: “1” in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to “1”, “10”, and “11”.
After concatenating them, we have “11011”, which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in “1101110010111011110001001101010111100”.
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

Constraints:

1 <= n <= $10^5$

解析

从$f(1) = 0b1 = 1$开始:

$ f(2) = 0b110 = 0b100 + 0b10 = f(1)<<2 + 0b10 = 1*4 + 2=6$

$f(3) = 0b11011 = 110 00 + 11 = f(2) << 2 + 3 = 24 + 3 = 27$

容易看出有以下递推公式:

$f(n) = f(n-1) <<[floor(log_2n)+1]+n = f(n-1) * 2^{\lfloor\log_2n\rfloor+1}+n$

这里的$\log_2n$是因为大于0的 k位2进制数个数有$2^{k-1}个$, 等比数列求和得 小于k位的二进制数 共有$2^k$个.

k=1 1 : $2^0=1$

k=2 10, 11: $2^{1} = 2$

k=3 100, 101, 110, 111: $2^2 = 4$

所以递推公示的左移位数是$\log_2n$向下取整 + 1.

用矩阵形式来表示就是

$\begin{pmatrix} 2^{1} & 1 &0\\ 0 & 1 &1\\ 0 & 0 &1\\ \end{pmatrix} \cdot \begin{pmatrix} f(1) \\ 2\\ 1 \\ \end{pmatrix} = \begin{pmatrix} (f(1)<<1) + 2 + 1 \\ 2 + 1\\ 1 \\ \end{pmatrix}$ $\begin{pmatrix} 2^{M} & 1 &0\\ 0 & 1 &1\\ 0 & 0 &1\\ \end{pmatrix} \cdot \begin{pmatrix} f(n-1) \\ n\\ 1 \\ \end{pmatrix} = \begin{pmatrix} (f(n-1)<<M) + n-1 + 1 \\ n + 1\\ 1 \\ \end{pmatrix}= \begin{pmatrix} f(n) \\ n+1\\ 1 \\ \end{pmatrix}$

然后只需要用结合律, 先考虑不同位数的二进制数生成的矩阵的$2^{k-1}$次乘方, 然后再去乘以向量$(f(1), 2,1)^T$.

另附英文讲解-and-O(log2-n)-fast-and-short-explained)一个.

代码

class Solution(object):
    def concatenatedBinary(self, n):
        """
        :type n: int
        :rtype: int
        """
        def multiply(X, Y):
            return [[sum(a*b for a,b in zip(X_row,Y_col)) % 1000000007 for Y_col in zip(*Y)] for X_row in X]
        
        ans, acc, level = [[1], [2], [1]], 1, 1
        while acc < n:
            M = 2 ** (level + 1)
			
			# number of matrix production in this level
            x = take = min(n, M - 1) - acc
            
			mat = [[M, 1, 0], [0, 1, 1], [0, 0, 1]]
			
			# for example
			# num^13 = num * num^4 * num^8
			# num^6 = num^2 * num^4
            while x > 0:
                if x & 1: ans = multiply(mat, ans)
                mat, x = multiply(mat, mat), x >> 1
            
			acc, level = acc + take, level + 1
        
        return ans[0][0]