Combinatorics API

template<typename T>
struct Combinatorics {
    int sz;
    Factorial<T> fact;
    
    Combinatorics(int n);  // Precompute factorials up to n
    
    T C(int n, int k);     // Combinations (nCr)
    T H(int n, int k);     // Combinations with repetition
    T P(int n, int k);     // Permutations (nPr)
    T P(int n, const vector<int> &m);  // Permutations with repetition
    T catalan(int n);      // n-th Catalan number
};

template<typename T>
using Comb = Combinatorics<T>;

template<typename T>
T C(int n, int k);

using Mint = Modular<integral_constant<int, MOD>>;
Comb<Mint> comb(1e6);

Mint result = comb.C(10, 3);  // 120
// Number of ways to choose 3 items from 10

template<typename T>
T C(T n, T k) {  // O(k)
    if(n < k) return static_cast<T>(0);
    T ans = static_cast<T>(1);
    for(T i = static_cast<T>(1); i <= k; i++) {
        ans *= (n - k + i);
        ans /= i;
    }
    return ans;
}

int result = C(10, 3);  // 120

// Symmetry
C(n, k) = C(n, n-k)

// Base cases
C(n, 0) = C(n, n) = 1

// Pascal's identity
C(n, k) = C(n-1, k-1) + C(n-1, k)

// Sum of row
C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n

template<typename T>
T P(int n, int k);

Comb<Mint> comb(1e6);
Mint result = comb.P(10, 3);  // 720
// Number of ways to arrange 3 items from 10

template<typename T>
T P(int n, const vector<int> &m);

// Permutations of "MISSISSIPPI"
vector<int> freq = {1, 4, 4, 2};  // M:1, I:4, S:4, P:2
Mint result = comb.P(11, freq);
// 11! / (1! * 4! * 4! * 2!) = 34650

template<typename T>
T H(int n, int k);

Comb<Mint> comb(1e6);
Mint result = comb.H(3, 2);  // 6
// Number of ways to choose 2 items from 3 types with repetition
// {A,A}, {A,B}, {A,C}, {B,B}, {B,C}, {C,C}

template<typename T>
T catalan(int n);

Comb<Mint> comb(1e6);
Mint result = comb.catalan(5);  // 42

bool next_combination(vector<int> &comb, int n);

vector<int> comb = {0, 1, 2};  // First combination of size 3 from 0 to n-1
do {
    // Process combination
    for(int i : comb) cout << i << " ";
    cout << endl;
} while(next_combination(comb, n));

vector<vector<int>> all_combinations(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int start) {
        if(current.size() == k) {
            result.push_back(current);
            return;
        }
        for(int i = start; i < n; i++) {
            current.push_back(i);
            backtrack(i + 1);
            current.pop_back();
        }
    };
    
    backtrack(0);
    return result;
}

vector<int> kth_permutation(int n, int k) {
    vector<int> result;
    vector<int> numbers;
    
    int fact = 1;
    for(int i = 1; i <= n; i++) {
        numbers.push_back(i);
        fact *= i;
    }
    
    k--;  // 0-indexed
    for(int i = 0; i < n; i++) {
        fact /= (n - i);
        int index = k / fact;
        result.push_back(numbers[index]);
        numbers.erase(numbers.begin() + index);
        k %= fact;
    }
    
    return result;
}

vector<int> perm = kth_permutation(4, 9);
// Returns the 9th permutation of {1, 2, 3, 4}
// Result: {2, 3, 1, 4}

template<typename T>
bool next_permutation_with_reps(vector<T> &arr);

vector<int> arr = {1, 1, 2};
do {
    for(int x : arr) cout << x << " ";
    cout << endl;
} while(next_permutation_with_reps(arr));
// Generates: 1 1 2, 1 2 1, 2 1 1

template<typename T>
T nCr_mod(int n, int r, T mod) {
    if(r > n) return 0;
    if(r == 0 || r == n) return 1;
    
    vector<T> C(r + 1, 0);
    C[0] = 1;
    
    for(int i = 1; i <= n; i++) {
        for(int j = min(i, r); j > 0; j--) {
            C[j] = (C[j] + C[j-1]) % mod;
        }
    }
    return C[r];
}