Đếm chuỗi ký tự từ R, G, B thỏa mãn điều kiện số lượng C++

Cho số lượng tối thiểu R, G, B và độ dài chuỗi size. Đếm số chuỗi có ít nhất R ký tự 'R', G ký tự 'G', B ký tự 'B'.

Ý tưởng

• Số ký tự còn lại: temp = size - (R + G + B).
• Phân phối temp ký tự dư cho 3 loại (i cho R, j cho B, temp-i-j cho G).
• Mỗi phân phối cho số hoán vị: size! / ((R+i)! * (B+j)! * (G+temp-i-j)!).
• Tổng hợp tất cả trường hợp.

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int combination(int R, int G, int B, int size) {
    int count = 0;
    int temp = size - (R + G + B);
    int arr[size + 1];
    arr[0] = 1;
    for (int i = 1; i <= size; i++)
        arr[i] = arr[i - 1] * i;
    for (int i = 0; i <= temp; i++) {
        for (int j = 0; j <= temp - i; j++) {
            int temp_2 = temp - (i + j);
            int temp_3 = arr[i + R] * arr[j + B] * arr[temp_2 + G];
            count += arr[size] / temp_3;
        }
    }
    return count;
}

int main() {
    int R = 2, G = 1, B = 1;
    int size = 4;
    cout << "Số chuỗi thỏa mãn: " << combination(R, G, B, size);
    return 0;
}

Kết quả

Số chuỗi thỏa mãn: 12