Stars and bars: сколько неотрицательных решений у x1+x2+...+xk = n?

Это «звёзды и палочки» (stars and bars). Представь n звёздочек в ряд и (k−1) палочек-перегородок, которые делят их на k групп. Любая расстановка перегородок ↔ одно решение. Всего объектов n + (k−1), выбираем, где стоят k−1 палочек:

Число неотрицательных решений = C(n + k − 1, k − 1) = C(n + k − 1, n).

Если каждый x_i ≥ 1 (ящики непусты), подставь x_i = y_i + 1, y_i ≥ 0: уравнение становится y_1+...+y_k = n − k, откуда ответ = C(n − 1, k − 1) (при n ≥ k, иначе 0).

// неотрицательные решения x1+...+xk = n
long long starsBars(int n, int k) {        // C(n+k-1, k-1)
    return C(n + k - 1, k - 1);            // C — через факториалы mod p
}
// положительные решения
long long starsBarsPositive(int n, int k) {
    if (n < k) return 0;
    return C(n - 1, k - 1);
}

Сложность — O(1) после предподсчёта факториалов. Обобщения с верхними границами на x_i решаются добавлением включения-исключения по «превышениям».