指定された問題では、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's and 0's for(auto x : s) { if(x == '1') count_1++; // frequency of 1's else count_0++; // frequency of 0's } if(count_1 == 0){ cout << "0\n"; // if string only consists of 0'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 サイトの他の関連記事を参照してください。