由前 n 个自然数的二进制表示连接而成的数字的十进制值。

huangapple go评论72阅读模式
英文:

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

问题

# 给定一个数 *n*,找到由前 *n* 个自然数的二进制表示连接而成的数的十进制值。
# 求答案对 10^9+7 取模。

# 此外,*n* 可以很大,高效的对数时间复杂度方法是必要的。

# 例:*n*=`4`,答案 = `220`

# **解释**:组成的数=`11011100` (`1=1`,`2=10`,`3=11`,`4=100`)。
# `11011100` 的十进制值=`"220"`。

def concatenate_binary_decimal(n):
    MOD = 10**9 + 7
    result = 0
    multiplier = 1
    for i in range(1, n + 1):
        binary_rep = bin(i)[2:]
        result = (result * (1 << len(binary_rep)) + int(binary_rep, 2)) % MOD
        multiplier = (multiplier * (1 << len(binary_rep)) + 1) % MOD
    return (result * multiplier) % MOD
英文:

> 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.

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

Eg: n=4, Answer = 220

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

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

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

答案1

得分: 8

This solution to this question requires O(N) time. Luckily this can be solved in O(logN) time. Also, this is the A047778 sequence:

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

The sequence follows this recurrence relation:
由前 n 个自然数的二进制表示连接而成的数字的十进制值。 where ⌊.⌋ is floor function

a(n) can also be expressed as a sum of multiple arithmetico–geometric series.

If we are interested in a(14), here's how it can be calculated.

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

Multiplying with powers of two on both sides of the above equations gives equations like the following:

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

If we add all the above equations, a(14) can be expressed as the sum of four arithmetico–geometric series.
由前 n 个自然数的二进制表示连接而成的数字的十进制值。

It's important to note that in all sequences except the first one, the first term of the arithmetic progression is of the form 由前 n 个自然数的二进制表示连接而成的数字的十进制值。 and the last term 由前 n 个自然数的二进制表示连接而成的数字的十进制值。

The sum of n terms of the arithmetico–geometric sequence can be calculated using this 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).

Since we're interested in a(n) mod 1000000007 and not the actual term a(n), these modulo arithmetics may come in handy.

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

This is a good starting point for implementing division modulo, which requires some number theory basics.

Once we figure out the number of sequences required and the five variables a, n, d, b, r for each sequence, a(n) modulo 1000000007 can be calculated in O(logn) time.

Here's a working C++ code:

#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;
}

The validity of the above C++ code can be verified using this trivial python code:

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)
英文:

This solution to this question requires O(N) time. Luckily this can be solved in O(logN) time. Also, this is the A047778 sequence:

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

The sequence follows this recurrence relation:
由前 n 个自然数的二进制表示连接而成的数字的十进制值。 where ⌊.⌋ is floor function

a(n) can also be expressed as sum of multiple arithmetico–geometric series.

If we are interested in a(14), here's how it can be calculated.

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

Multiplying with powers of two on both sides of the above equations gives equations like the following:

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

If we add all the above equations, a(14) can be expressed as sum of four arithmetico–geometric series.
由前 n 个自然数的二进制表示连接而成的数字的十进制值。

It's important to note that in all sequences except the first one, the first term of the arithmetic progression is of form 由前 n 个自然数的二进制表示连接而成的数字的十进制值。 and the last term 由前 n 个自然数的二进制表示连接而成的数字的十进制值。

The sum of n terms of arithmetico–geometric sequence can be calculated using this 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). 

Since we're interested in a(n) mod 1000000007 and not the actual term a(n), these modulo arithmetics may come in handy.

由前 n 个自然数的二进制表示连接而成的数字的十进制值。

This is a good starting point for implementing division modulo which requires some number theory basics.

Once we figure out the number of sequences required and the five variables a, n, d, b, r for each sequence, a(n) modulo 1000000007 can be calculated in O(logn) time.

Here's a working C++ code :

#include &lt;numeric&gt;
#include &lt;iostream&gt;
#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,&amp;x1,&amp;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, &amp;x, &amp;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 &gt;&gt;= 1;
bitCountOfN--;
}
std::cout &lt;&lt; ans &lt;&lt; std::endl;
return 0;
}

The validity of the above C++ code can be verified using this trivial python code :

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

答案2

得分: 6

注意,使用字符串表示在任务变更后并不必要(而且在任务变更后没有用处)。看一下位运算的方法(使用Python,但原理是相同的)。

对于新的模1000000007的条件,我们只需在每一步的结果计算行中添加模运算,因为左移和按位或操作相当于乘以二的幂并加法,这些操作遵守模属性的等价关系。注意,中间结果不会超过1000000007*n,因此long类型在这里适用于合理的n值。

n = 100
size = 0   #加数的位长度
result = 0   # 长累加器
for i in range(1, n + 1):
    if i & (i - 1) == 0:    #对于2的幂,我们增加位长度
        size += 1
    result = ((result << size) | i) % 1000000007   #将累加器左移并用新的加数填充低位
print(result)

不使用位运算的变体:

pow2 = 1
nextpow = 2
result = 0   # 长累加器
for i in range(1, n + 1):
    if i == nextpow:    #对于2的幂,我们增加位长度
        pow2 = nextpow
        nextpow = nextpow * 2
    result = (result * pow2  + i) % 1000000007  #将累加器左移并用新的加数填充低位
英文:

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)

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 &amp; (i - 1) == 0:    #for powers of two we increase bit length
size += 1
result = ((result &lt;&lt; size) | i) % 1000000007   #shift accumulator left and fill low bits with new addend
print(result)

variant without bitwise operations:

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

答案3

得分: -1

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;
英文:
    cin&gt;&gt;n;
ll ans=1;
ll one=1;
for(int i=2;i&lt;=n;i++)
{
ll digit=log2(i)+1;
ans=(((ans%N*(one&lt;&lt;digit)%N)%N+i%N)%N);
}
cout&lt;&lt;ans&lt;&lt;Ed;

huangapple
  • 本文由 发表于 2020年6月29日 13:34:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/62631840.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定