Pythonで1からnまでの2進数表現を連結した値を求めるプログラム

問題概要

整数 n が与えられたとき、1 から n までの各数値を2進数表現に変換し、それらを順番に連結してできる2進文字列の10進数としての値を求めます。答えが非常に大きくなる場合は、10⁹ + 7 で割った余りを返します。

例えば、n = 4 の場合を考えてみましょう。1 から 4 までの2進数表現を順に連結すると、次のようになります。

"1" + "10" + "11" + "100" = "110111000"

この2進数「110111000」を10進数に変換すると 220 になります。これが求める答えです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 答え ans を 1 で初期化します(最初の「1」に相当)。
• 剰余を取るための定数 m を 10⁹ + 7 とします。
• i を 2 から n まで順に処理します。
  • ans を i のビット長分だけ左シフトします。
  • ans に i を加算し、m で割った余りを取ります。
• 最終的な ans を返します。

ポイント解説

左シフト演算(ans << i.bit_length())を行うと、ans の2進表現の末尾に i のビット長分だけ 0 が追加されます。そこに i を加算することで、i の2進表現がそのまま末尾に連結されたことになります。つまり、文字列を実際に結合しなくても、ビット演算だけで高速に連結処理を実現できるのがこの手法の魅力です。

実装例(Python)

以下がPythonでの実装例です。

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

計算量について

ループは 2 から n まで合計 n 回程度実行されるため、時間計算量は O(n) となります。また、使用する変数は ans と m のみなので、空間計算量は O(1) です。大きな n に対しても効率的に動作する実装といえます。