C++でバイナリ文字列の「1」から始まる一意な順列の数を求める方法

この記事では、0と1で構成される文字列が与えられたとき、「1」で始まる順列の総数を求める問題を解説します。答えは非常に大きな数になる可能性があるため、1000000007で割った余り(mod)を出力します。

入力 : str = "10101001001"
出力 : 210

入力 : str = "101110011"
出力 : 56

本記事では、組み合わせ論(コンビネーション)の知識を応用し、この問題を解くための数式を導き出すことで解決していきます。

解法のアプローチ

まず、文字列に含まれる「0」と「1」の個数をそれぞれ数えます。ここで、文字列内の1の個数を n、0の個数を m、与えられた文字列の長さを L とおくと、この問題を解くための公式は次のように表せます。

(L−1)! / ((n−1)! × m!)

C++での実装例

#include <bits/stdc++.h>
#define MOD 1000000007 // 1e9 + 7 をMODとして定義

using namespace std;

long long fact(long long n) {
   if(n <= 1)
   return 1;
   return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
int main() {
   string s = "101110011";
   long long L = s.size(); // 与えられた文字列の長さ
   long long count_1 = 0, count_0 = 0; // 1と0の個数をカウント
   for(auto x : s) {
      if(x == '1')
         count_1++; // 1の出現頻度
      else
         count_0++; // 0の出現頻度
   }
   if(count_1 == 0){
      cout << "0\n"; // 文字列が0のみで構成されている場合、答えは0
   } else {
      long long factL = fact(L-1); // (L-1)!
      long long factn = fact(count_1 - 1); // (n-1)!
      long long factm = fact(count_0); // m!
      long long ans = factL / (factn * factm); // 公式を適用
      cout << ans << "\n";
   }
   return 0;
}

出力

56

このプログラムの時間計算量は O(N) です。ここで N は与えられた文字列の長さを表します。

コードの解説

このアプローチでは、まず文字列内に含まれる1と0の個数をそれぞれ数えます。そのうえで、先頭に「1」を1つ固定して配置し、残りの長さ L−1 の部分における0と1のすべての可能な順列を考えます。これにより、(L−1)! / ((n−1)! × m!) という公式が導かれます。ここで、(n−1)! は残りの1の並べ方の総数、m! は0の並べ方の総数に対応します。

なお、階乗の値をMODで割った余り同士で除算を行う場合、厳密にはモジュラ逆元を用いる必要があります。上記のコードは入力サイズが小さければ正しく動作しますが、大きな入力に対応させる場合はフェルマーの小定理などを利用した逆元計算を組み合わせるとより安全です。

まとめ

本記事では、組み合わせ論を応用した数式を構築することで、バイナリ文字列が「1」で始まる一意な順列の数を求める問題を解きました。

また、この問題を解くためのC++プログラムと完全なアプローチについても学びました。同じロジックはC、Java、Pythonなど他の言語でも実装できます。本記事が皆さんの学習の一助となれば幸いです。