英文:
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
="220"
.
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);
答案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:
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.
Multiplying with powers of two on both sides of the above equations gives equations like the following:
If we add all the above equations, a(14)
can be expressed as the sum of four
arithmetico–geometric series.
It's important to note that in all sequences except the first one, the first term of the arithmetic progression is of the form and the last term
The sum of n terms of the arithmetico–geometric sequence can be calculated using this 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).
Since we're interested in a(n) mod 1000000007
and not the actual term a(n)
, these modulo arithmetics may come in handy.
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:
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.
Multiplying with powers of two on both sides of the above equations gives equations like the following:
If we add all the above equations, a(14)
can be expressed as sum of four
arithmetico–geometric series.
It's important to note that in all sequences except the first one, the first term of the arithmetic progression is of form and the last term
The sum of n terms of arithmetico–geometric sequence can be calculated using this 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).
Since we're interested in a(n) mod 1000000007
and not the actual term a(n)
, these modulo arithmetics may come in handy.
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)
答案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 & (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)
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>>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;
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论