java - 通过连接前 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

This solution这道题需要 O(N) 时间。幸运的是，这可以在 O(logN) 时间内解决。另外，这是 A047778顺序:

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

序列遵循以下递归关系: 其中 ⌊.⌋ 是 floor function

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

如果我们对 a(14) 感兴趣，下面是计算方法。

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

如果我们将上述所有方程相加，a(14) 可以表示为四个 算术-几何级数的和。

重要的是要注意，在除第一个序列之外的所有序列中，等差级数的第一项的形式为 和最后一项

可以使用这个 formula 计算算术-几何数列的 n 项之和:

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)