Hiểu bài toán

Bài toán mô phỏng sự lây lan của Covid-19. Ban đầu có 1 người nhiễm. Sau mỗi ngày, mỗi người nhiễm sẽ lây cho K người khác (và sau đó bị cách ly, không lây tiếp). Hỏi sau N ngày có tổng cộng bao nhiêu người nhiễm.

Quy tắc:

• Ngày 0: 1 người.
• Các ngày tiếp theo: Số người nhiễm mới bằng số người nhiễm ngày trước đó nhân với K.
• N = 0: Kết quả là 1.
• K = 0: Nếu N > 0, kết quả là 0 (vì không có sự lây lan).
• Kết quả lấy số dư modulo 2021.

Công thức tổng quát: Số người nhiễm sau N ngày là tổng của các cấp số nhân: Total = 1 + K + K^2 + ... + K^N Nếu K = 1, Total = N + 1.

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

Cách Mô phỏng lặp (Dùng cho K=0)

#include <iostream>
using namespace std;

int main() {
    long long K, N;
    cin >> K >> N;

    if (K == 0) {
        cout << 0 << endl;
        return 0;
    }
    if (N == 0) {
        cout << 1 << endl;
        return 0;
    }

    long long sum = 1;
    long long term = 1;

    for (int i = 0; i < N; i++) {
        term = (term * K) % 2021;
        sum = (sum + term) % 2021;
    }

    cout << sum << endl;
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất, mô phỏng chính xác quá trình lây lan từng ngày. Với mỗi ngày, ta tính số người nhiễm mới (term) bằng cách nhân số người nhiễm ngày trước với K, sau đó cộng vào tổng. Với N và K lên tới 10^9, phương pháp này sẽ quá thời gian chạy (Time Limit Exceeded) vì vòng lặp chạy quá lâu. Tuy nhiên, đây là nền tảng để hiểu bản chất bài toán.

Cách Công thức toán học (Tổng cấp số nhân)

#include <iostream>
using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 2021;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 2021;
        base = (base * base) % 2021;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 2021 - 2); // Fermat's Little Theorem
}

int main() {
    long long K, N;
    cin >> K >> N;

    if (K == 0 && N > 0) {
        cout << 0;
        return 0;
    }
    if (N == 0) {
        cout << 1;
        return 0;
    }

    long long ans;
    if (K == 1) {
        ans = (N + 1) % 2021;
    } else {
        // Cong thuc: (K^(N+1) - 1) / (K - 1)
        long long tu = (power(K, N + 1) - 1 + 2021) % 2021;
        long long mau = modInverse(K - 1);
        ans = (tu * mau) % 2021;
    }

    cout << ans;
    return 0;
}

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

Sử dụng công thức tổng quát của tổng cấp số nhân: S = (K^(N+1) - 1) / (K - 1). Để tính nhanh K^(N+1) với N lớn, ta dùng thuật toán Lũy thừa nhanh (Fast Exponentiation) với độ phức tạp O(log N). Vì phép chia trong modulo (với số mũ lớn) không đơn giản, ta phải dùng phép nhân với số nhân (modular inverse). Do Modulo là 2021 (số nguyên tố), ta có thể tính số nhân modulo của (K-1) bằng cách nâng lên lũy thừa theo định lý Fermat nhỏ: (K-1)^(2019) mod 2021. Ngoài ra, phải xử lý riêng trường hợp K=1 vì công thức tổng quát bị chia cho 0 (lúc này tổng là N+1).

Cách Tối ưu với K chia hết cho 2021

// Logic kiểm tra đặc biệt
if (K % 2021 == 0) {
    // K là bội của 2021 nên K^1, K^2... đều = 0 mod 2021
    // Tổng chỉ còn lại số 1 ban đầu
    cout << 1;
} else {
    // Dùng công thức tổng quát
}

• Time Complexity: O(1) hoặc O(log N)
• Space Complexity: O(1)

Trong giải pháp của phanvanchung, tác giả đã sử dụng một biến x3 = k - 1 và x4 = 1931 (số mũ này có vẻ là tối ưu hóa cho số mũ âm hoặc lỗi logic). Tuy nhiên, một trường hợp đặc biệt quan trọng mà các solution trên có thể bỏ qua hoặc xử lý ngầm: Nếu K là bội của 2021 (ví dụ K = 2021), thì K % 2021 = 0.

• Sau ngày 1: Số người nhiễm thêm = 0.
• Tổng số người nhiễm sau N ngày (với N >= 1) chỉ là 1 (người ban đầu). Các solution khác có thể không gặp vấn đề này vì phép nhân trong code của họ % 2021 ngay lập tức, nên K=2021 sẽ thành 0, và vòng lặp hoặc phép tính power sẽ trả về 0 đúng.

Điểm khác biệt giữa các solution:

• Solution 1 (LonggVuz): Mô phỏng lặp N lần nhưng có nhân modulo (Vẫn TLE nếu N lớn thực sự, nhưng code mẫu có vẻ bị truncate và logic vòng lặp for(int i=0; i<n; i++) là sai nếu n=10^9).</li>
• Solution 3 (phanvanchung): Cố gắng dùng công thức lượng giác/ma trận nhưng có vẻ code sai logic số mũ (1931) và cách viết power trôi dẫn đến kết quả sai.

Giải pháp tối ưu và đúng đắn nhất là dùng Lũy thừa nhanh kết hợp tổng cấp số nhân như Approach 2.

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

Bài học kinh nghiệm

• Bài toán quy về tổng cấp số nhân: 1 + K + ... + K^N.
• Với N, K lớn (10^9), không thể mô phỏng tuần tự. Cần dùng công thức toán học.
• Công thức (K^(N+1) - 1) / (K - 1) yêu cầu tính số nhân modulo, chỉ áp dụng được khi K-1 và Modulo nguyên tố cùng nhau.
• Phải xử lý riêng các trường hợp K=0, K=1, N=0.

Lỗi thường gặp

• Quên xử lý trường hợp K=1 (vì K-1=0, không thể dùng công thức tổng quát).
• Quên xử lý trường hợp K=0 (công thức tổng quát sẽ ra 1/(-1) = -1, không đúng với logic bài toán).
• Lỗi logic khi tính số nhân modulo: (a/b) mod m không phải là (a mod m) / (b mod m).
• Overflow biến dữ liệu: Phải dùng kiểu long long và thực hiện phép nhân modulo liên tục.