class Solution {
public:
int concatenatedBinary(int n) {
}
};
1680. 连接连续二进制数字
给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 7 取余的结果。
示例 1：
输入：n = 1 输出：1 解释：二进制的 "1" 对应着十进制的 1 。
示例 2：
输入：n = 3 输出：27 解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。 将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：
输入：n = 12 输出：505379714 解释：连接结果为 "1101110010111011110001001101010111100" 。 对应的十进制数字为 118505380540 。 对 109 + 7 取余后，结果为 505379714 。
提示：
1 <= n <= 105原站题解
rust 解法, 执行用时: 44 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-14 15:00:05
impl Solution {
pub fn concatenated_binary(n: i32) -> i32 {
let mut shift:u128=0;
let mut res:u128=0;
let MOD:u128 = 1000000007;
for i in 1..n+1{
if i&(i-1) ==0{ //判断i是否是2的幂
shift+=1;
}
res = (res%MOD<<shift)+i as u128;
}
(res%MOD) as i32
}
}
python3 解法, 执行用时: 680 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-14 14:54:36
class Solution:
def concatenatedBinary(self, n: int) -> int:
ans = 0
for i in range(1, n+1):
ans = (ans<<i.bit_length() | i) % (10 ** 9 + 7)
return ans
python3 解法, 执行用时: 64 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-14 14:49:07
class Solution:
def concatenatedBinary(self, n: int) -> int:
mod = 10**9 + 7
zeroes = 0
ans = 0
for k in range(64, 1, -1): # 任意 64 位无符号整数都可以秒出答案
if (lb := 2 ** (k - 1)) <= n:
t = n - lb
u = pow(2, t * k, mod)
v = pow(2 ** k - 1, mod - 2, mod)
w = pow(2, (t + 1) * k, mod)
x = pow(2, zeroes, mod)
ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod
zeroes += (t + 1) * k
n = lb - 1
ans += pow(2, zeroes, mod)
return ans % mod
python3 解法, 执行用时: 1104 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-14 14:48:38
class Solution:
def concatenatedBinary(self, n: int) -> int:
mod = 10**9 + 7
# ans 表示答案，shift 表示 len_{2}(i)
ans = shift = 0
for i in range(1, n + 1):
# if 131072 % i == 0:
if (i & (i - 1)) == 0:
shift += 1
ans = ((ans << shift) + i) % mod
return ans
golang 解法, 执行用时: 36 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-14 14:47:42
func concatenatedBinary(n int) (ans int) {
for i := 1; i <= n; i++ {
ans = (ans<<bits.Len(uint(i)) | i) % (1e9 + 7)
}
return
}