問題描述

給定一個數n，找出由前n個自然數的二進制表示連接形成的數的十進制值.
打印答案模 10^9+7.

Given a number n, find the decimal value of the number formed by concatenating the binary representations of first n natural numbers.
Print answer modulo 10^9+7.

另外，n 可以大到 10^9，因此需要對數時間方法.

Also, n can be as big as 10^9 and hence logarithmic time approach is needed.

例如:n=4，答案 = 220

說明:數字形成=11011100 (1=1,2=10,3=11,4=100).11011100=220" 的十進制值.

Explanation: Number formed=11011100 (1=1,2=10,3=11,4=100). Decimal value of 11011100="220".

我在下面使用的代碼僅適用于第一個整數 N<=15

The code I am using below only works for first integers N<=15

    String input = "";
    for(int i = 1;i<=n;i++) {
        input += (Integer.toBinaryString(i));
    }
    return Integer.parseInt(input,2);

推薦答案

請注意，使用字符串表示不是必需的(此外，在任務更改后沒有用處).看按位算術的方法(Python，但原理是一樣的)

Note that working with string representation is not necessary (moreover, is not useful after task changing). Look at approach with bitwise arithmetics (Python, but principle is the same)

有了關于模 1000000007 的新條件，我們只需在每一步的結果計算行中添加模運算，因為左移和 or-ing 相當于乘以 2 的冪再加，這些運算服從模的等價關系特性.注意中間結果不超過1000000007*n，所以long類型適合這里合理的n值.

With new condition concerning modulo 1000000007 we have just add modulo operation to result calculation line at every step, because shift left and or-ing is equivalent to multiplication by power of two and adding, these operations are obeyed to equivalence relations for modulo properties. Note that intermediate results don't exceed 1000000007*n, so long type is suitable here for reasonable n values.

n = 100  
size = 0   #bit length of addends
result = 0   # long accumulator
for i in range(1, n + 1):    
    if i & (i - 1) == 0:    #for powers of two we increase bit length
        size += 1
    result = ((result << size) | i) % 1000000007   #shift accumulator left and fill low bits with new addend
print(result)

沒有按位運算的變體:

pow2 = 1
nextpow = 2
result = 0   # long accumulator
for i in range(1, n + 1):
    if i == nextpow:    #for powers of two we increase bit length
        pow2 = nextpow
        nextpow = nextpow * 2
    result = (result * pow2  + i) % 1000000007  #shift accumulator left and fill low bits with new addend

這篇關于通過連接前 n 個自然數的二進制表示形成的數字的十進制值的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！