1. Hợp nhất các khoảng quy tắc

• Mục đích: Tránh tính trùng lặp các bước nhảy từ các quy tắc giao nhau.
• Cách thực hiện:
  • Sắp xếp các khoảng theo điểm bắt đầu.
  • Hợp nhất các khoảng chồng lấn thành một khoảng liên tục. Ví dụ: \([1, 3]\) và \([2, 5] \Rightarrow [1, 5]\).

1. Quy hoạch động (DP) kết hợp Prefix Sum

• Mảng \(dp[i]\):

  • Lưu số cách nhảy đến ô \(i\).
  • Khởi tạo: \(dp[1] = 1\) (vì bắt đầu từ ô 1).

• Mảng \(prefix\_sum[i]\):

  • Lưu tổng \(dp[1] + dp[2] + \dots + dp[i]\).
  • Giúp tính tổng các giá trị \(dp\) trong một khoảng \(O(1)\) thay vì \(O(n)\).

1. Xử lý từng ô \(i\) từ 2 đến \(n\)

• Với mỗi ô \(i\), xét từng khoảng đã hợp nhất \([L, R]\).

• Xác định các ô \(j\) có thể nhảy đến \(i\) qua quy tắc \([L, R]\):

  \(j \in [i - R, i - L]\)

• Tính tổng số cách từ các ô \(j\) này đến \(i\) bằng \(prefix\_sum\):

  \(sum = prefix\_sum[right] - prefix\_sum[left - 1]\)

• Trong đó:

  \(left = \max(1, i - R)\)

  \(right = i - L\)

• Cập nhật:

  \(dp[i] = sum\)

1. Đảm bảo kết quả modulo

• Tất cả phép toán được thực hiện modulo \(10^9 + 7\) để tránh tràn số.

Ví dụ minh họa

• Input: \(n = 7, k = 1\), quy tắc \([2, 4]\)
• Output: \(4\)

Các bước tính toán:

1. Hợp nhất quy tắc \([2, 4]\).
2. Khởi tạo: \(dp[1] = 1\), \(prefix\_sum[1] = 1\).
3. Tính \(dp[2]\):
   • Không có quy tắc nào áp dụng → \(dp[2] = 0\).

4. Tính \(dp[3]\):

   \(j \in [3 - 4, 3 - 2] = [1, 2]\)

   \(left = 1, \quad right = 1\)

   \(sum = prefix\_sum[1] - prefix\_sum[0] = 1\)

   \(dp[3] = 1\)

5. Tính \(dp[4]\):

   \(j \in [4 - 4, 4 - 2] = [0, 2]\)

   \(left = 1, \quad right = 2\)

   \(sum = prefix\_sum[2] - prefix\_sum[0] = 1\)

   \(dp[4] = 1\)

6. Lặp lại đến \(dp[7]\) → Kết quả cuối cùng là \(4\).

Độ phức tạp

• Thời gian: \(O(n \cdot m)\), với \(m\) là số khoảng đã hợp nhất.
• Không gian: \(O(n)\), do sử dụng hai mảng \(dp\) và \(prefix\_sum\).

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

const int MOD = 1e9 + 7;

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());
    vector<pair<int, int>> merged;
    merged.push_back(intervals[0]);
    for (size_t i = 1; i < intervals.size(); ++i) {
        auto& last = merged.back();
        if (intervals[i].first <= last.second) {
            last.second = max(last.second, intervals[i].second);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

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

    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> intervals(k);
    for (int i = 0; i < k; ++i) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    vector<pair<int, int>> merged = mergeIntervals(intervals);

    vector<long long> dp(n + 1, 0);
    vector<long long> pre_sum(n + 1, 0);

    dp[1] = 1;
    pre_sum[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = 0;
        for (const auto& interval : merged) {
            int l = interval.first;
            int r = interval.second;
            int a = i - r;
            int b = i - l;

            int left = max(1, a);
            int right = b;

            if (left > right) continue;

            long long sum = (pre_sum[right] - (left > 1 ? pre_sum[left - 1] : 0)) % MOD;
            if (sum < 0) sum += MOD;

            dp[i] = (dp[i] + sum) % MOD;
        }
        pre_sum[i] = (pre_sum[i - 1] + dp[i]) % MOD;
    }

    cout << dp[n] % MOD << '\n';

    return 0;
}