Python程式：連線連續二進位制數

假設我們有一個數字n，我們需要找到透過將1到n的二進位制表示依次連線而成的二進位制字串的十進位制值。如果結果太大，則返回結果模10^9 + 7。

例如，如果輸入n = 4，則輸出為220，因為將1到4的二進位制表示連線起來的結果為 "1" + "10" + "11" + "100" = 11011100，這是220的二進位制表示。

為了解決這個問題，我們將遵循以下步驟：

  • ans := 1
  • m := 10^9+7
  • 對於範圍從2到n的i，執行：
    • ans := 將ans左移（i的位數）位
    • ans := (ans+i) mod m
  • 返回 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

更新於：2021年10月6日

440 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告