C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다.-C++-php.cn

C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다.

PHPz

풀어 주다： 2023-09-05 09:01:06

앞으로

1195명이 탐색했습니다.

C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다.

주어진 문제에서 0과 1로 구성된 문자열이 주어졌습니다. 1로 시작하는 모든 순열의 총 개수를 찾아야 합니다. 대답은 엄청난 숫자일 수 있으므로 모듈로 1000000007을 가져와 출력합니다.

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

로그인 후 복사

조합 수학을 적용하고 몇 가지 공식을 설정하여 이 문제를 해결할 것입니다.

해결 방법

이 방법에서는 0과 1의 수를 계산합니다. 이제 n은 문자열에 나타나는 1의 수이고, m은 문자열에 나타나는 0의 수이며, L은 주어진 문자열의 길이라고 가정합니다. 따라서 이 문제를 해결하기 위해 공식화하는 공식은 다음과 같습니다. 1 )!/ (n-1)!.

Example

#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;
}

로그인 후 복사

Output

로그인 후 복사

주어진 프로그램의 시간 복잡도는 O(N)입니다. 여기서 n은 주어진 문자열의 길이입니다.

위 코드 설명

이 방법에서는 문자열에서 1과 0의 수를 세고 이제 시작 부분에 1을 넣은 다음 길이 L-1과 1 순열의 문자열에서 가능한 모든 0을 공식화합니다. 이 순열을 공식화하면 (L-1)!/(n-1)!*m!의 공식을 얻을 수 있습니다. 여기서 (n-1)!은 나머지 1의 순열입니다.