สมมติว่าเรามีตัวเลข n เราต้องหาค่าทศนิยมของสตริงไบนารีโดยการต่อเลขฐานสองแทนค่า 1 ถึง n ตามลำดับ ถ้าคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนโมดูโลคำตอบ 10^9 + 7
ดังนั้น หากอินพุตมีค่าเท่ากับ n =4 เอาต์พุตจะเป็น 220 เพราะการต่อแทนค่าไบนารีจาก 1 ถึง 4 จะเป็น "1" + "10" + "11" + "100" =110111000 ค่านี้เป็นไบนารี แทน 220.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- แทน :=1
- ม :=10^9+7
- สำหรับฉันในช่วง 2 ถึง n ทำ
- ans :=เปลี่ยน ans (ความยาวบิตของ i) จำนวนครั้ง
- ans :=(ans+i) mod m
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
