C++ で書かれており、1 から始まるバイナリ文字列の一意の順列の数を見つけます。

指定された問題では、0 と 1 で構成される文字列が与えられており、1 から始まるすべての順列の合計数を見つける必要があります。答えは膨大な数になる可能性があるため、1000000007 を法にして出力します。

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

いくつかの組み合わせ数学を適用し、いくつかの公式を確立することによって、この問題を解決します。

解決方法

この方法では、0と1の数を数えます。ここで、n が文字列に現れる 1 の数、m が文字列に現れる 0 の数、L が指定された文字列の長さであると仮定します。したがって、この問題を解決するために定式化する式は (L- 1 )!/ (n-1)! * m!。

例

#include <bits/stdc++.h>
#define MOD 1000000007 // defining 1e9 + 7 as 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(); // length of given string
   long long count_1 = 0, count_0 = 0; // keeping count of 1&#39;s and 0&#39;s
   for(auto x : s) {
      if(x == &#39;1&#39;)
         count_1++; // frequency of 1&#39;s
      else
        count_0++; // frequency of 0&#39;s
   }
   if(count_1 == 0){
      cout << "0\n"; // if string only consists of 0&#39;s so our answer will be 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); // putting the formula
      cout << ans << "\n";
   }
   return 0;
}

出力

56

指定されたプログラムの時間計算量は O(N) です。ここで、n は指定された文字列の長さです。

上記のコードの説明

このメソッドでは、文字列内の 1 と 0 の数を数えます。今度は先頭と L-1 Formulate の長さに 1 を置きます。文字列内の 0 と 1 の可能なすべての順列。この順列を定式化すると、(L-1)! / (n-1)! * m! という式が得られます。ここで、(n-1)! は残りの 1 つの順列です。 , m! は 0 の順列です。

結論

この記事では、いくつかの組み合わせ論を適用して式を定式化することにより、1 から始まるバイナリ文字列の一意の順列の数を見つける問題を解決しました。

C プログラムと、この問題を解決するための完全な方法 (通常の方法) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ で書かれており、1 から始まるバイナリ文字列の一意の順列の数を見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。