โปรแกรมหาตัวเลขจากการต่อบाइनารีของ 1 ถึง n ใน Python

สมมติว่าเรามีตัวเลข n เราต้องหาค่าทศนิยมของสตริงไบนารีที่ได้จากการต่อตัวแทนไบนารีของ 1 ถึง n ทีละตัวตามลำดับ ถ้าคำตอบใหญ่เกินไป return คำตอบ modulo 10^9 + 7

เช่น ถ้าอินพุตคือ n = 4 ผลลัพธ์จะเป็น 220 เพราะการต่อไบนารีจาก 1 ถึง 4 จะเป็น "1" + "10" + "11" + "100" = 110111000 ซึ่งเป็นไบนารีของ 220

วิธีแก้ปัญหา

• ans := 1
• m := 10^9+7
• สำหรับ i ในช่วง 2 ถึง n:
  • ans := shift ans (bit length ของ i) ครั้ง
  • ans := (ans + i) mod m
• return ans

ตัวอย่าง

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

อินพุต

4

เอาต์พุต

220