通过连接前 n 个自然数的二进制表示形式形成的数字的十进制值
kar*_*hik 2 java math binary mod
给定一个数n，找出通过连接前n 个自然数的二进制表示形式形成的数字的十进制值。
打印答案模 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);
这个问题的解决方案需要O(N)时间。幸运的是，这可以及时解决O(logN)。此外，这是A047778序列：
1,6,27,220,1765,14126,113015,1808248,28931977, 462911642,7406586283,118505380540,1896086088653, 30337377418462,485398038695407,15532737238253040, 497047591624097297,15905522931971113522
该序列遵循此递推关系：
在哪里 ？。？是楼层功能
a(n)也可以表示为多个算术几何级数的和。
如果我们对 感兴趣a(14)，这里是它的计算方法。
在上述等式两边同时乘以 2 的幂得到如下等式：
如果将上述所有方程a(14)相加，可以表示为four算术-几何级数之和。
需要注意的是，在除第一个序列之外的所有序列中，等差数列的第一项的形式为 
和最后一个学期 
可以使用以下公式计算算术几何序列的 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)，这些模算术可能会派上用场。
这是实现需要一些数论基础知识的除法模的一个很好的起点。
一旦我们计算出所需的序列数量和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)
请注意，不需要使用字符串表示（此外，在任务更改后也没有用）。看看按位算术的方法（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