Hiểu bài toán

Yêu cầu: Đếm số cách chia N viên kẹo cho 3 anh em (Hiếu, Kiệt, Hoàng) sao cho:

1. Tổng số kẹo bằng N.
2. Không ai có 0 viên.
3. Cả 3 có số kẹo phân biệt (không ai giống ai).
4. Hiếu (anh cả) có ít kẹo nhất, Hoàng (em út) có nhiều kẹo nhất.

Gọi số kẹo của Hiếu, Kiệt, Hoàng lần lượt là x, y, z. Ta có:

• x + y + z = N
• 0 < x < y < z

Ta cần tìm số bộ (x, y, z) nguyên dương dương thỏa mãn phương trình và bất phương trình trên.

Các cách tiếp cận

Cách Biến đổi tổ hợp (Công thức tổng quát)

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

long long solve(long long n) {
    if (n < 6) return 0;
    n -= 6;
    long long d = n / 6;
    long long r = n % 6;

    // Cong thuc: d*(d+1)/2 * 6 + r*(d+1) + (r==0 ? 1 : 0)
    // Phan tich duoi MOD
    long long term1 = (d % MOD) * ((d + 1) % MOD) % MOD;
    term1 = term1 * 500000004 % MOD; // 500000004 là số nhân nghịch đảo của 2 % MOD
    term1 = term1 * 6 % MOD;

    long long term2 = (r % MOD) * ((d + 1) % MOD) % MOD;

    long long term3 = (r == 0 ? 1 : 0);

    return (term1 + term2 + term3) % MOD;
}

int main() {
    long long n;
    cin >> n;
    cout << solve(n);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đặt các biến mới để đơn giản hóa bất phương trình:

1. Đặt a = x, b = y - x - 1, c = z - y - 1. Khi đó a >= 1, b >= 0, c >= 0. Phương trình trở thành: a + (a + b + 1) + (a + b + c + 2) = N => 3a + 2b + c = N - 3. Đặt k = N - 3. Vấn đề chuyển thành tìm số bộ (a, b, c) không âm thỏa mãn 3a + 2b + c = k.

1. Xét các trường hợp dựa trên phần dư của k khi chia cho 6 (BCNN của 3, 2, 1). Nếu k = 6d + r (0 <= r < 6), số lượng nghiệm là: N(d, r) = d(d+1)/2 * 6 + r(d+1) + (r == 0 ? 1 : 0)

Công thức này được suy ra bằng cách đếm số lượng nghiệm của a, b, c dựa trên tổng. Ví dụ: Với r=0, d>=1, số cách là 6 * (1+2+...+d). Với r=0, d=0, số cách là 1. Phép chia và nhân modulo cần thực hiện cẩn thận.

Cách Giải thích trực quan (Quy hoạch)

// Pseudocode for understanding logic
#include <iostream>
using namespace std;

int main() {
    long long N; cin >> N;
    long long ans = 0;
    // Duyệt a (số kẹo Hiếu)
    for (long long a = 1; 3*a + 3 <= N; a++) {
        long long rem = N - 3*a - 3; // N - (a + (a+1) + (a+2))
        // Hoặc tổng quát hơn: rem = N - 3a - 3
        // Yêu cầu: b >= 0, c >= 0, 2b + c = rem
        // Số cách là floor(rem/2) + 1
        ans += rem / 2 + 1;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phân tích bài toán theo biến a (số kẹo của Hiếu). Xét a là số kẹo của Hiếu. Do Hiếu ít nhất, Kiệt nhiều hơn Hiếu, Hoàng nhiều nhất, ta có:

• Hiếu = a
• Kiệt >= a + 1
• Hoàng >= Kiệt + 1 >= a + 2

Tổng tối thiểu cho một giá trị 'a' là a + (a+1) + (a+2) = 3a + 3. Nếu N < 3a + 3 thì không thể chia tiếp.

Nếu N >= 3a + 3: Số kẹo còn lại sau khi chia tối thiểu là Rem = N - (3a + 3). Gọi x = Kiệt - (a+1) và y = Hoàng - (Kiệt + 1). Ta có x >= 0, y >= 0. Phân bổ Rem còn lại cho Kiệt và Hoàng sao cho Kiệt vẫn nhỏ hơn Hoàng. Rem = x + y + (số kẹo bù để Hoàng > Kiệt). Thực chất bài toán quy về tìm số bộ (x, y) không âm sao cho (a+1+x) < (a+2+x+y). Điều này luôn đúng nếu y >= 0. Số cách chia Rem cho Kiệt và Hoàng (với Kiệt >= 1, Hoàng >= Kiệt + 1) tương đương với số cách viết Rem dưới dạng tổng của 2 số không âm. Số cách là (Rem / 2) + 1.

Tổng hợp lại: Đếm tổng (Rem / 2 + 1) cho đến khi 3a + 3 > N.

Vì N rất lớn (10^18), duyệt tuần tự là không khả thi. Tuy nhiên, phân tích này cho thấy quy luật tuyến tính của nghiệm theo a, dẫn đến công thức tổng quát ở Approach 1.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm số nghiệm không âm của phương trình tuyến tính: 3a + 2b + c = N - 3 (với a >= 1, b, c >= 0).
• Vì N rất lớn (10^18), lời giải phải có độ phức tạp O(1) hoặc O(log N), không thể dùng quy hoạch động hoặc duyệt.
• Số cách chia có quy luật lặp lại theo chu kỳ 6 (BCNN của các hệ số 3, 2, 1 trong phương trình), dẫn đến công thức tổng quát.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (int, long long) gây tràn số khi N = 10^18. Cần dùng unsigned long long hoặc __int128.
• Lỗi chia lấy dư khi phép chia cho số không phải ước của Modulo (ví dụ chia cho 2). Cần nhân với số nhân nghịch đảo (inverse modular).
• Quên xử lý trường hợp N quá nhỏ (N < 6) không có lời giải.