通过连接前 n 个自然数的二进制表示形式形成的数字的十进制值

Question

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，因此需要对数时间方法。

例如：n=4，答案=220

解释: 形成的数字=11011100 (1=1,2=10,3=11,4=100) . 11011100="220".

的十进制值

我在下面使用的代码仅适用于第一个整数 N<=15

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

Answer 1

请注意，使用字符串表示不是必需的（此外，在任务更改后也没有用）。看看按位算术的方法（Python，但原理是一样的）

关于模1000000007的新条件我们只是在每一步的结果计算行上加上模运算，因为左移和或运算相当于乘以2的幂和相加，这些运算服从等价关系对于模属性。请注意，中间结果不会超过 1000000007*n，因此 long 类型适用于此处合理的 n 值。

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

Answer 2

    cin>>n;
    ll ans=1;
    ll one=1;
    for(int i=2;i<=n;i++)
    {
        ll digit=log2(i)+1;
        ans=(((ans%N*(one<<digit)%N)%N+i%N)%N);
    }
    cout<<ans<<Ed;

Answer 3

to this question requires O(N) time. Luckily this can be solved in O(logN) time. Also, this is the A047778序列：

1,6,27,220,1765,14126,113015,1808248,28931977, 462911642,7406586283,118505380540,1896086088653, 30337377418462,485398038695407,15532737238253040, 497047591624097297,15905522931971113522

序列遵循以下递归关系： where ⌊.⌋ is floor function

a(n)也可以表示为多个arithmetico–geometric series.

的和

如果我们对 a(14) 感兴趣，请按以下方式计算。

在上述等式两边乘以2的幂得到如下等式：

如果我们将以上所有方程相加，a(14)可以表示为four等差级数的和。

重要的是要注意，在除第一个序列之外的所有序列中，等差级数的第一项的形式为 and the last term

等差数列n项之和可以用这个formula :

a(First term of AP), n(Number of terms), d(Common Difference of AP), b(First term of GP), r(Common ratio of GP).

由于我们对 a(n) mod 1000000007 而不是实际术语 a(n) 感兴趣，因此这些模运算可能会派上用场。

This 是实现除法取模的良好起点，它需要一些数论基础知识。

一旦我们计算出所需序列的数量和每个序列的五个变量 a, n, d, b, r，a(n) modulo 1000000007 可以在 O(logn) 时间内计算出来。

这是一个有效的 C++ 代码：

#include <numeric>
#include <iostream>
#define mod long(1e9+7)

long multiply(long a,long b){
    a%= mod;b%= mod;
    return (a*b)%mod;
}

void inverseModulo(long a,long m,long *x,long *y){ //ax congruent to 1 mod m

    if(!a){
        *x=0;
        *y=1;
        return ;
    }
    long x1,y1;
    inverseModulo(m%a,a,&x1,&y1);
    *x=y1-(m/a)*x1;
    *y=x1;
    return;
}

long moduloDivision(long a,long b,long m){  // (a*(returnValue))mod m congruent to b mod m
    //https://www.geeksforgeeks.org/modular-division/ and https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
    long x,y;
    inverseModulo(b, m, &x, &y);
    x%=m;
    return (x*a)%m;
}

long power(long n,long r){ //calculates (n^r)%mod in logarithmic time
    if(r==0) return 1;
    if(r==1) return n;
    if(r%2){
        auto tmp=power(n, (r-1)/2);
        return multiply(multiply(n,tmp),tmp);
    }
    auto tmp=power(n, r/2);
    return multiply(tmp, tmp);
}
long sumOfAGPSeries(long a,long d,long b,long r,long n){
    if(r==1) return multiply(n, multiply(a, 2)+multiply(n-1, d))/2;
    long left=multiply(multiply(d, r), power(r,n-1)-1);
    left=a+moduloDivision(left,r-1,mod);
    left=multiply(left, b);
    left%=mod;
    long right=multiply(multiply(b, power(r, n)), a+multiply(n-1, d));
    long ans=right-left;
    ans=(ans%mod + mod) % mod;
    return moduloDivision(ans,r-1,mod);

}
signed main(){
    long N=1000;
    long ans = 0;
    long bitCountOfN = log2(N) + 1;
    long nearestPowerOfTwo = pow(2, bitCountOfN - 1);
    long startOfGP = 0;
    while (nearestPowerOfTwo) { // iterating over each arithmetico–geometric sequence
        long a, d, b, r, n;
        a = N;
        d = -1;
        b = power(2, startOfGP);
        r = power(2, bitCountOfN);
        n = N - nearestPowerOfTwo + 1;
        ans += sumOfAGPSeries(a, d, b, r, n);
        ans %= mod;
        startOfGP += n * bitCountOfN;
        N = nearestPowerOfTwo - 1;
        nearestPowerOfTwo >>= 1;
        bitCountOfN--;
    }
    std::cout << ans << std::endl;
    return 0;
}

上述 C++ 代码的有效性可以使用这个简单的 python 代码来验证：

def a(n): 
  return int("".join([(bin(i))[2:] for i in range(1, n+1)]), 2)
for n in range(1,100):
  print (a(n)%1000000007)

通过连接前 n 个自然数的二进制表示形式形成的数字的十进制值

decimal value of the number formed by concatenating the binary representations of first n natural numbers

java

math

binary

mod