Hiểu bài toán

Bài toán mô tả quá trình đặt sỏi trên một đoạn thẳng. Ban đầu có 2 viên. Sau mỗi lượt N, ta thêm sỏi vào vị trí trung điểm của mọi cặp sỏi liền kề. Với N rất lớn (đến $10^{18}$), ta cần tìm chữ số cuối cùng của tổng số viên sỏi sau $N$ lượt. Qua phân tích quy luật, số sỏi sau $N$ lượt là $2^N + 1$. Do đó, bài toán quy về tìm $(2^N + 1) \pmod{10}$.

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

Cách Quy hoạch động theo lượt (Không khả thi)

int main() {
    long long N;
    cin >> N;
    long long stones = 2;
    for (long long i = 1; i <= N; i++) {
        stones = 2 * stones - 1;
    }
    cout << stones % 10;
}

• Time Complexity: O(N) - Quá chậm với N <= 10^18
• Space Complexity: O(1)

Approach này mô phỏng lại quá trình đặt sỏi. Nếu $Si$ là số sỏi sau lượt $i$, thì $S{i+1} = 2Si - 1$ (vì có $Si - 1$ khoảng trống giữa các sỏi, mỗi khoảng thêm 1 viên). Giải công thức này ta được $S_N = 2^N + 1$. Tuy nhiên, nếu chỉ mô phỏng vòng lặp, độ phức tạp là $O(N)$, quá lớn để chạy với $N=10^{18}$. Approach này chỉ dùng để tìm quy luật chứ không dùng để giải quyết bài toán.

Cách Tính nhanh lũy thừa modulo 10

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

int main() {
    long long n;
    cin >> n;
    if (n == 0) {
        cout << 2 << endl;
        return 0;
    }
    int cycle[] = {6, 2, 4, 8};
    cout << (cycle[n % 4] + 1) % 10 << endl;
    return 0;
}

• Time Complexity: O(1) hoặc O(log N) tùy cách đọc input
• Space Complexity: O(1)

Đây là giải pháp tối ưu. Ta biết số sỏi là $2^N + 1$. Để tìm chữ số cuối, cần tính $(2^N + 1) \pmod{10}$. Lũy thừa $2^N \pmod{10}$ có chu kỳ lặp lại sau 4 số: 2, 4, 8, 6. Tùy vào $N \pmod 4$, ta lấy giá trị tương ứng từ mảng chu kỳ, cộng thêm 1, rồi lấy số cuối. Nếu $N=0$, $2^0 = 1$, tổng là 2. Với $N>0$, chu kỳ này hoạt động chính xác.

Cách Xử lý số lớn (Big Integer mod 4)

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

int main() {
    string s;
    cin >> s;
    int rem = 0;
    for (char c : s) {
        rem = (rem * 10 + (c - '0')) % 4;
    }
    if (rem == 0) rem = 4;
    int cycle[] = {2, 4, 8, 6};
    int p = cycle[rem - 1];
    cout << (p + 1) % 10 << endl;
    return 0;
}

• Time Complexity: O(L) - L là độ dài số N
• Space Complexity: O(1)

Trong trường hợp $N$ quá lớn không thể lưu vào long long (ví dụ $N$ là string với độ dài lớn), ta cần tính $N \pmod 4$ bằng cách duyệt qua các chữ số của $N$. Logic tính $2^N \pmod{10}$ vẫn dựa trên chu kỳ 4. Sau khi có $N \pmod 4$, ta suy ra $2^N \pmod{10}$ và cộng 1. Đây là cách xử lý tổng quát nhất cho input dạng số lớn.

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

Bài học kinh nghiệm

• Quy luật số sỏi: Nếu có $k$ viên sỏi ở lượt trước, ở lượt này có $k$ khoảng trống giữa chúng, thêm $k-1$ viên mới. Tổng: $k + (k-1) = 2k - 1$. Quy nạp được công thức tổng quát $S_N = 2^N + 1$.
• Chu kỳ modulo 10: Lũy thừa $2^N \pmod{10}$ có chu kỳ lặp lại sau 4 số: 2, 4, 8, 6 (với $N > 0$). Do đó chỉ cần quan tâm đến $N \pmod 4$.
• Xử lý số lớn: Với $N$ lên tới $10^{18}$, ta dùng long long hoặc unsigned long long là đủ. Tuy nhiên, để an toàn tuyệt đối với các bài toán tương tự có $N$ lớn hơn, tính $N \pmod 4$ từ string là kỹ thuật cần biết.

Lỗi thường gặp

• Trường hợp N = 0: Chu kỳ lũy thừa 2^N thường bắt đầu từ N=1 là 2. Nếu N=0, $2^0 = 1$, tổng là 2. Cần xử lý riêng hoặc mảng chu kỳ đúng.
• Sai quy luật: Lầm tưởng số sỏi là $2^{N+1}$ hay $2^N$ thay vì $2^N + 1$. Phải vẽ ra hoặc suy luận kỹ quy luật $S{i+1} = 2Si - 1$.
• Lỗi trích xuất chu kỳ: Mảng chu kỳ {6, 2, 4, 8} chỉ đúng khi map với N % 4 đúng quy ước. Ví dụ N % 4 == 0 -> 6, N % 4 == 1 -> 2...