Chương trình tìm nối chuỗi nhị phân liên tiếp trong Python

Cho số n, tìm giá trị thập phân của chuỗi nhị phân ghép từ biểu diễn nhị phân của 1 đến n theo thứ tự. Kết quả modulo 10^9+7.

Ví dụ: n = 4, đầu ra = 220 vì "1"+"10"+"11"+"100" = "110111000" = 220.

Giải pháp

Dịch bit và cộng dồn:

• ans := 1, m := 10^9+7
• Với i từ 2 đến n:
  • ans := ans << i.bit_length()
  • ans := (ans + i) % m
• Trả về ans

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(n):
    ans = 1
    m = (10**9+7)
    for i in range(2, n+1):
        ans = ans << i.bit_length()
        ans = (ans + i) % m
    return ans

n = 4
print(solve(n))

Đầu vào

4

Đầu ra

220