Hiểu bài toán

Bài toán yêu cầu tính một số hạng thứ n (n rất lớn, lên tới 10^18) của một dãy số được định nghĩa bởi một quy hoạch tuyến tính cấp k (Linear Recurrence Relation). Dãy số này được xác định bởi:

• k số hạng đầu tiên: c1, c2, ..., c_k.
• Quy tắc tính các số hạng tiếp theo (i > k): ai = α1a_{i-k} + α_2a{i-k+1} + ... + αk*a{i-1}. Đề bài cho trước k, các hệ số α, các số hạng đầu c, và m truy vấn nj. Với mỗi truy vấn, cần tính a{nj} modulo 10^9 + 7.

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

Cách Ma trận lũy thừa (Matrix Exponentiation)

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAXK = 15;

int k, m;
ll alpha[MAXK], c[MAXK];
ll n_queries[105];

struct Matrix {
    ll mat[MAXK][MAXK];
    Matrix() {
        memset(mat, 0, sizeof(mat));
    }
};

// Nhân hai ma trận
Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            ll sum = 0;
            for (int z = 0; z < k; z++) {
                sum = (sum + A.mat[i][z] * B.mat[z][j]) % MOD;
            }
            C.mat[i][j] = sum;
        }
    }
    return C;
}

// Tính ma trận lũy thừa n
Matrix power(Matrix A, ll p) {
    Matrix res;
    for (int i = 0; i < k; i++) res.mat[i][i] = 1; // Ma trận đơn vị
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

ll solve(ll n) {
    if (n <= k) return c[n - 1];

    // Xây dựng ma trận chuyển trạng thái T
    Matrix T;
    // Hàng 0: xây dựng a_{i+1} từ a_{i-k+1} ... a_i
    // Theo đề bài: a_i = sum(alpha_j * a_{i-k+j-1}) (với j từ 1 đến k)
    // Trạng thái vector V_i = [a_{i}, a_{i-1}, ..., a_{i-k+1}]^T
    // V_{i+1} = T * V_i
    // a_{i+1} = alpha_1 * a_{i-k+1} + ... + alpha_k * a_i
    // Do vector đang là [a_i, a_{i-1}, ..., a_{i-k+1}]
    // a_{i+1} = alpha_k * a_i + alpha_{k-1} * a_{i-1} + ... + alpha_1 * a_{i-k+1}

    for (int j = 0; j < k; j++) {
        T.mat[0][j] = alpha[k - 1 - j];
    }

    // Các hàng còn lại (shift)
    for (int i = 1; i < k; i++) {
        T.mat[i][i - 1] = 1;
    }

    // Tính T^(n-k)
    Matrix Tk = power(T, n - k);

    // Kết quả a_n là phần tử đầu tiên của T^(n-k) * [c_k, c_{k-1}, ..., c_1]^T
    // (Lưu ý thứ tự c trong vector đầu vào phải khớp với thứ tự trong ma trận)
    // Vector ban đầu: V_k = [a_k, a_{k-1}, ..., a_1] = [c_k, c_{k-1}, ..., c_1]

    ll res = 0;
    for (int i = 0; i < k; i++) {
        res = (res + Tk.mat[0][i] * c[k - 1 - i]) % MOD;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> k >> m;
    for (int i = 0; i < k; i++) cin >> alpha[i];
    for (int i = 0; i < k; i++) cin >> c[i];
    for (int i = 0; i < m; i++) cin >> n_queries[i];

    for (int i = 0; i < m; i++) {
        cout << solve(n_queries[i]) << (i == m - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

• Time Complexity: O(k^3 * log(n))
• Space Complexity: O(k^2)

Đây là cách tiếp cận chuẩn để giải quy hoạch tuyến tính cấp k với n lớn. Ta biểu diễn quy luật truy hồi dưới dạng nhân ma trận. Gọi vector trạng thái là Vi = [ai, a{i-1}, ..., a{i-k+1}]^T. Ta cần tìm ma trận chuyển trạng thái T sao cho V{i+1} = T * Vi.

• Ma trận T có kích thước k x k.
• Hàng đầu của T chứa các hệ số α theo thứ tự ngược lại (vì vector đang sắp xếp giảm dần chỉ số: a_i ở đầu).
• Các hàng còn lại là các vector dịch chuyển (shift) để đưa a{i-1}, ..., a{i-k+1} xuống hàng dưới.
• Để tìm an, ta tính T^(n-k) * Vk.
• Việc tính lũy thừa ma trận được thực hiện trong O(k^3 * log(n)) bằng phương pháp chia đôi (binary exponentiation).
• Do n có thể lên tới 10^18, lũy thừa ma trận là bắt buộc.

Cách Tối ưu Bessel (Matrix Exponentiation Optimization)

• Time Complexity: O(k^2 * log(n))
• Space Complexity: O(k^2)

Khi k nhỏ (k ≤ 10), việc tối ưu ma trận lũy thừa có thể được thực hiện bằng cách tối ưu phép nhân ma trận. Tuy nhiên, do ma trận T là ma trận đặc biệt (ma trận companion), có thể tối ưu phép nhân xuống O(k^2) thay vì O(k^3) nếu khéo léo, nhưng trong thực tế với k nhỏ, việc tối ưu trực tiếp ma trận lũy thừa O(k^3 log n) đã đủ nhanh.

Một phương pháp khác là sử dụng công thức Bessel hoặc các thuật toán nhanh hơn cho quy hoạch tuyến tính (như Berlekamp-Massey để tìm đa số sinh, nhưng ở đây quy luật đã cho sẵn).

Giải pháp này về cơ bản vẫn là Ma trận lũy thừa, nhưng có thể được tối ưu hóa trong việc nhân ma trận nếu k lớn hơn, hoặc sử dụng các thư viện số học nâng cao. Trong các bài nộp mẫu, cách tiếp cận này là phổ biến nhất.

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

Bài học kinh nghiệm

• Bài toán quy hoạch tuyến tính cấp k với n lớn luôn có lời giải bằng ma trận lũy thừa.
• Giá trị n nhỏ (n ≤ k) cần được xử lý riêng để tránh lỗi logic.
• Thứ tự các phần tử trong vector trạng thái phải nhất quán với ma trận chuyển đổi.

Lỗi thường gặp

• Sai lệch chỉ số mảng (0-based vs 1-based) khi chuyển đổi từ công thức toán học sang code.
• Quên modulo 10^9 + 7 dẫn đến tràn số (overflow) với các biến long long.