Tóm tắt đề bài

Cho mảng độ dài \(n\), mỗi phần tử \(a_i \in [1, M]\). Hãy đếm số mảng sao cho tồn tại ít nhất một đoạn liên tiếp dài \(K\) mà tất cả phần tử trong đoạn đó bằng nhau. Kết quả lấy modulo \(10^9+7\).

Phân tích

• Tổng số mảng là \(M^n\) (rất lớn, cần modulo).
• Bài toán yêu cầu đếm mảng có ít nhất một đoạn \(K\) phần tử giống nhau.
• Ý tưởng chuẩn là đếm bù:
  • Đếm số mảng không có đoạn \(K\) phần tử liên tiếp giống nhau (tức là mọi “run” liên tiếp cùng giá trị đều có độ dài \(\le K-1\)).
  • Kết quả cần tìm \(=\) $M^n - \text{(số mảng không có đoạn dài \(K\))}$.
• Ràng buộc \(n, M, K \le 10^6\) nên cần thuật toán \(O(n)\) và bộ nhớ tuyến tính hoặc tối ưu.

Các trường hợp đặc biệt quan trọng:

• Nếu \(K > n\): không thể có đoạn dài \(K\) \(\Rightarrow\) đáp án \(0\).
• Nếu \(K = 1\): mọi mảng đều có đoạn dài \(1\) giống nhau \(\Rightarrow\) đáp án \(M^n\).

Hướng giải quyết

Nhận xét & Định nghĩa DP

Gọi \(dp[i]\) là số mảng độ dài \(i\) không chứa đoạn \(K\) phần tử liên tiếp giống nhau.

Khi đó:

• Đáp án cần tìm:

Ta cần tìm công thức truy hồi cho \(dp[i]\).

Các giá trị cơ sở

• Với \(i < K\): chắc chắn không thể có đoạn dài \(K\) nên:

• Với \(i = K\): chỉ có các mảng “toàn giống nhau” mới vi phạm, có đúng \(M\) mảng dạng (x, x, ..., x):

Code AC hiện thực đúng hai phần này.

Công thức truy hồi cho \(i > K\)

Xét xây dựng mảng độ dài \(i\) từ mảng độ dài \(i-1\) (đều đang “tốt”, không có run dài \(K\)).

• Nếu ta lấy mọi mảng tốt độ dài \(i-1\) và thêm một phần tử bất kỳ (\(M\) cách), ta có \(M \cdot dp[i-1]\) mảng độ dài \(i\).
• Nhưng trong số đó có những mảng mới tạo ra vi phạm (tạo ra một run dài đúng \(K\) ở cuối). Ta cần trừ đi số mảng “bị hỏng” này.

Một mảng độ dài \(i\) sẽ vừa mới tạo ra một đoạn \(K\) phần tử giống nhau ở cuối khi và chỉ khi:

• \(K\) phần tử cuối cùng đều bằng một giá trị \(x\),
• và phần tử ngay trước đoạn đó (vị trí \(i-K\)) khác \(x\) (nếu bằng thì run còn dài hơn và bản thân tiền tố \(i-1\) đã vi phạm, không thuộc \(dp[i-1]\)).

Đếm số mảng “bị hỏng”:

• Chọn một mảng tốt độ dài \(i-K\) (có \(dp[i-K]\) cách).
• Chọn giá trị tại vị trí \(i-K\) (gọi là \(y\)) đã nằm trong mảng đó, và chọn \(x \ne y\) để lấp \(K\) phần tử cuối: có đúng \((M-1)\) cách chọn \(x\) khác với phần tử cuối của tiền tố.
  • Trực giác: với mỗi tiền tố tốt độ dài \(i-K\), ta có thể “kéo dài” bằng cách gắn thêm một khối \(K\) phần tử bằng nhau với giá trị khác phần tử trước khối, khi đó chắc chắn tạo run dài \(K\) ở cuối.

Vì vậy số mảng bị hỏng là \((M-1)\cdot dp[i-K]\).

Suy ra:

Đây đúng là công thức trong code AC:

• term1 = dp[i-1] * m
• term2 = dp[i-k] * (m-1)
• dp[i] = term1 - term2 (mod)

Tính \(M^n\)

Code đồng thời duy trì biến total_arrays để tính dần \(M^i\) theo vòng lặp:

• bắt đầu từ \(1\),
• mỗi bước nhân thêm \(M\) và lấy modulo,
• cuối cùng có \(total\_arrays = M^n \bmod MOD\).

Kết quả:

• valid_arrays = dp[n] là số mảng không có đoạn \(K\) phần tử giống nhau,
• result = total_arrays - valid_arrays là số mảng có ít nhất một đoạn như vậy.

Lưu ý/Pitfall thường gặp

• Phải xử lý modulo cẩn thận với phép trừ: cộng thêm MOD trước khi % MOD.
• Trường hợp \(K=1\) là đặc biệt (nếu áp công thức sẽ gặp mâu thuẫn vì mọi mảng đều “vi phạm” ngay lập tức).
• \(n\) tới \(10^6\) nên dùng I/O nhanh và mảng/vector kích thước \(n+1\).

Độ phức tạp

• Thời gian: \(O(n)\)
• Bộ nhớ: \(O(n)\) để lưu mảng \(dp[0..n]\)

Code tham khảo

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

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

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    if (k > n) {
        // Không thể tồn tại đoạn K phần tử liên tiếp nếu n < K
        cout << 0 << '\n';
        return 0;
    }

    if (k == 1) {
        // K=1: mọi mảng đều có một đoạn dài 1 các phần tử giống nhau
        long long total = 1;
        for (int i = 0; i < n; i++) total = (total * m) % MOD;
        cout << total << '\n';
        return 0;
    }

    vector<long long> dp(n + 1);
    long long total_arrays = 1; // sẽ giữ M^i theo i tăng dần

    // dp[i] = M^i với i < k (không thể có đoạn dài k)
    for (int i = 0; i < k; i++) {
        if (i > 0) total_arrays = (total_arrays * m) % MOD; // total_arrays = M^i
        dp[i] = total_arrays;
    }

    // i = k: dp[k] = M^k - M (trừ các mảng toàn giống nhau)
    total_arrays = (total_arrays * m) % MOD; // M^k
    dp[k] = (total_arrays - m + MOD) % MOD;

    // i > k: dp[i] = m*dp[i-1] - (m-1)*dp[i-k]
    for (int i = k + 1; i <= n; i++) {
        total_arrays = (total_arrays * m) % MOD; // cập nhật M^i

        long long term1 = (dp[i - 1] * m) % MOD;
        long long term2 = (dp[i - k] * (m - 1)) % MOD;
        dp[i] = (term1 - term2 + MOD) % MOD;
    }

    long long valid_arrays = dp[n]; // số mảng KHÔNG có đoạn k phần tử giống nhau
    long long result = (total_arrays - valid_arrays + MOD) % MOD; // đếm bù

    cout << result << '\n';
    return 0;
}