Số mảng kích thước N tổng bằng K (số nguyên dương) C++

Cho N và K. Đếm số mảng kích thước N gồm các số nguyên dương mà tổng bằng K.

Đây là bài toán tổ hợp kinh điển: số cách = C(K-1, N-1) (chia K vật giống nhau vào N hộp khác rỗng).

Ví dụ

• N=1, K=2 → 1 mảng: [2]
• N=2, K=4 → 3 mảng: [1,3], [2,2], [3,1]

Thuật toán

• Tính giai thừa.
• Áp dụng công thức tổ hợp C(K-1, N-1) = (K-1)! / ((N-1)! * (K-N)!).

Triển khai C++

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

long long factorial(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

long long getNumberOfArraysCount(int n, int k) {
    // C(k-1, n-1)
    return factorial(k - 1) / (factorial(n - 1) * factorial(k - n));
}

int main() {
    int N = 5, K = 8;
    cout << getNumberOfArraysCount(N, K) << endl; // Output: 35
    return 0;
}

Kết quả

35

Lưu ý: Với N, K lớn cần dùng modulo hoặc tính tổ hợp hiệu quả hơn để tránh tràn số.