C++で0と1のみからなる長さNの2進文字列の総数を求める方法

ある整数 num が与えられたとき、0と1のみで構成される長さ num の2進文字列が何通り作れるかを求めるのが本記事の課題です。

2進数（バイナリ）は数値表現の手法のひとつで、デジタルシステムにおいて最も広く利用されています。2進数は、「開く／閉じる」の2状態しか持たないスイッチのように、動作状態が2つしかないデバイスで表現できる量を扱うために用いられます。

2進数体系で使われる記号は 0 と 1 の2種類だけです。2進文字列とは、これらの2進値（0または1）のみから構成される文字列のことを指します。

例

入力 − num = 3
出力 − count is 8

説明 − 長さ3で作れる2進文字列の組み合わせは、000、111、001、101、100、110、011、010 の合計8通りです。したがって答えは8になります。

入力 − num = 2
出力 − count is 4

説明 − 長さ2で作れる2進文字列の組み合わせは、00、11、01、10 の合計4通りです。したがって答えは4になります。

プログラムで使用するアプローチ

長さ N の2進文字列の総数は、各桁で 0 か 1 のいずれかを選べるため 2^N 通り になります。N が非常に大きくなる可能性を考慮し、剰余 10⁹ + 7 を取りながら、繰り返し二乗法（バイナリ累乗法）によって O(log N) で高速に計算します。手順は以下のとおりです。

• 桁数が大きくなる可能性があるため、long long 型で数値を入力として受け取る

• 剰余演算用の mod 値を (long long)(1e9 + 7) として定義する

• 個数を計算する関数を作成する

• 結果を格納する変数を宣言し、1 で初期化する

• num > 0 の間ループを回す

• num & 1（最下位ビットが1＝指数が奇数）の場合、result = (result * x) % mod とする

• num = num >> 1（指数を半分にする）

• x = (x * x) % mod（底を二乗する）

• ループ終了後、result を返す

• 結果を出力する

コード例

#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// (x^y)%p を O(log y) で求める反復関数
ll power(ll x, ll y, ll p){
    ll result = 1;
    x = x % p; // x が p 以上の場合は更新しておく
    while (y > 0){
        // y が奇数の場合、result に x を掛ける
        if (y & 1){
            result = (result * x) % p;
        }
        // ここで y は必ず偶数
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return result;
}
// 2進文字列の個数を数える関数
ll countbstring(ll num){
    int count = power(2, num, mod);
    return count;
}
int main(){
    ll num = 3;
    cout <<"count is: "<<countbstring(num);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

count is: 8

この実装の時間計算量は O(log N)、空間計算量は O(1) です。繰り返し二乗法により、N が非常に大きな値であっても効率的に 2^N mod (10⁹+7) を求められる点がポイントです。