問題描述

給定一個(gè)數(shù)n，找出由前n個(gè)自然數(shù)的二進(jìn)制表示連接形成的數(shù)的十進(jì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，因此需要對數(shù)時(shí)間方法.

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

例如:n=4，答案 = 220

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

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

我在下面使用的代碼僅適用于第一個(gè)整數(shù) 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);

推薦答案

請注意，使用字符串表示不是必需的(此外，在任務(wù)更改后沒有用處).看按位算術(shù)的方法(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)

有了關(guān)于模 1000000007 的新條件，我們只需在每一步的結(jié)果計(jì)算行中添加模運(yùn)算，因?yàn)樽笠坪?or-ing 相當(dāng)于乘以 2 的冪再加，這些運(yùn)算服從模的等價(jià)關(guān)系特性.注意中間結(jié)果不超過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)

沒有按位運(yùn)算的變體:

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

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