Cho một chuỗi gồm các ký tự '0' và '1'. Yêu cầu tìm tổng số hoán vị sao cho chuỗi bắt đầu bằng '1'. Vì kết quả có thể rất lớn, ta in ra kết quả modulo 1.000.000.007.
Input: str = "10101001001" → Output: 210 Input: str = "101110011" → Output: 56
Ta sẽ giải quyết bằng tổ hợp toán học và xây dựng công thức tính toán.
Phương pháp giải
Đếm số lượng '0' (gọi là m) và '1' (gọi là n) trong chuỗi. Độ dài chuỗi là L. Ta cố định '1' ở vị trí đầu tiên, khi đó còn lại L-1 vị trí cần sắp xếp với (n-1) số '1' và m số '0'. Số hoán vị là công thức tổ hợp:
Kết quả = (L-1)! / ((n-1)! × m!)
Ví dụ minh họa
#include <bits/stdc++.h>
#define MOD 1000000007
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;
for (auto x : s) {
if (x == '1') count_1++;
else count_0++;
}
if (count_1 == 0) {
cout << "0\n";
} else {
long long factL = fact(L-1);
long long factn = fact(count_1 - 1);
long long factm = fact(count_0);
long long ans = factL / (factn * factm);
cout << ans << "\n";
}
return 0;
}
Kết quả
56
Độ phức tạp thời gian: O(N) với N là độ dài chuỗi.
Giải thích mã
Ta đếm số '1' và '0', đặt một '1' ở đầu, sau đó tính số hoán vị của (L-1) ký tự còn lại với (n-1) số '1' và m số '0'. Công thức chính là (L-1)! / ((n-1)! × m!).
Kết luận
Bài viết đã giải quyết bài toán tìm số hoán vị duy nhất bắt đầu bằng 1 của chuỗi nhị phân bằng tổ hợp toán học. Chương trình C++ có thể chuyển sang C, Java, Python, v.v. Hy vọng hữu ích cho bạn.