使用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的數量，現在我們在開頭放置一個1，並且現在在長度為L-1的字串中製定所有可能的0和1的排列，透過制定這個排列，我們得到(L-1)!/ (n-1)! * m!的公式，其中(n-1)!是剩餘1的排列，m!是0的排列。

結論

在本文中，我們透過應用一些組合數學並製定一個公式來解決了一個問題，即找到以1開頭的二進位字串的唯一排列數。

我們也學習了解決這個問題的C 程式和完整的方法（正常方法）。我們可以用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望您會發現本文有幫助。

以上是使用C++編寫，找到以1開頭的二進位字串的唯一排列數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！