นับสตริงที่ประกอบด้วย R, G, B ตามเงื่อนไขจำนวนขั้นต่ำ ใน C++

โจทย์: ต้องการสร้างสตริงความยาว size จากตัวอักษร 'R', 'G', 'B' โดยต้องมี R อย่างน้อย r ตัว, G อย่างน้อย g ตัว, B อย่างน้อย b ตัว

แนวคิด: Combinatorics

ให้ remaining = size - (r + g + b) เป็นตัวอักษรที่เหลือจัดสรรได้อิสระ
นับจำนวนวิธีแจก remaining ให้กับ 3 ตัวอักษร (stars and bars) แล้วคูณด้วยจำนวน permutation ของแต่ละการแจก

สูตร

สำหรับการแจกเพิ่ม i ให้ R, j ให้ B, k = remaining-i-j ให้ G:

จำนวนวิธี = size! / ((r+i)! × (g+k)! × (b+j)!)

รวมทุกค่า i, j ที่เป็นไปได้

โค้ด C++

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

int combination(int R, int G, int B, int size) {
    int count = 0;
    int remaining = size - (R + G + B);
    if (remaining < 0) return 0;
    
    // Precompute factorials
    vector<long long> fact(size + 1);
    fact[0] = 1;
    for (int i = 1; i <= size; i++)
        fact[i] = fact[i-1] * i;
    
    for (int i = 0; i <= remaining; i++) {
        for (int j = 0; j <= remaining - i; j++) {
            int k = remaining - i - j;
            long long denom = fact[R+i] * fact[G+k] * fact[B+j];
            count += fact[size] / denom;
        }
    }
    return count;
}

int main() {
    int R = 2, G = 1, B = 1;
    int size = 4;
    cout << "Count: " << combination(R, G, B, size);
    return 0;
}

ผลลัพธ์

Count of number of strings (made of R, G and B) using given combination are: 12

ตัวอย่างที่ 1

R=1, G=1, B=1, size=3 → remaining=0
Permutations ของ RGB = 3! = 6

ตัวอย่างที่ 2

R=2, G=0, B=2, size=4 → remaining=0
Permutations ของ RRBB = 4!/(2!2!) = 6

หมายเหตุ: โค้ดต้นฉบับใช้ int array สำหรับ factorial อาจ overflow ได้ ควรใช้ long long