# Tóm tắt đề
Cho $3$ số nguyên dương $n, m, k$. Chọn ra $n$ số nguyên dương sao cho mỗi số có giá trị không lớn hơn $m$ và $2$ số có vị trí kề nhau phải có độ chênh lệch không quá $k$.
Hay nói cách khác là dựng $a_1,a_2,\dots,a_n$ sao cho $1 \leq a_i \leq m$ và $\lvert a_i-a_{i+1} \rvert \leq k$ $\forall$$i$ $(1 \leq i \leq n)$.

**Yêu cầu:** Đếm số cách dựng ra các dãy thoả mãn điều kiện

# Lời Giải
### Subtask 1: $n \leq 5, m \leq 5$
Đệ quy quay lui thử mọi trường hợp tạo dãy là xong.
Độ phức tạp sẽ là $O(m^n)$

### Subtask 2: $n \leq 100, m \leq 100$
Sử dụng kĩ thuật **quy hoạch động (DP)** để giải quyết, ta gọi $dp[i][j]$ là tổng số cách khi đã duyệt qua $(i-1)$ phần tử và phần tử thứ $i$ có giá trị là $j$.
Công thức truy hồi sẽ là $dp[i][j]=dp[i][j]+dp[i-1][h]$ $\forall$$h$ $(max(1,j-k) \leq h \leq min(m,j+k))$.
Bài toán cơ sở sẽ là $dp[1][j]=1$ $\forall$$j$ ($1 \leq j\leq m)$.
Vì với mỗi vị trí $i$ mà chọn giá trị $j$ thì vị trí $(i-1)$ bắt buộc phải có những giá trị từ $max(1,j-k) \to min(m,j+k)$.
Vậy kết quả là $\sum_{i=1}^m dp[n][i]$
**Độ phức tạp:** $O(n*m^2)$

### Subtask 3: $n \leq 1000, m \leq 1000$
Tương tự như subtask $2$ nhưng chúng ta cùng nghĩ đến cách cải tiến.
Đầu tiên là ta có thể cải tiến độ phức tạp bộ nhớ, ta thấy rằng với chiều thứ nhất ta chỉ cần lưu giá trị $(i-1)$ và $i$ nên ta chỉ cần lưu $2$ mảng $dp[]$ $1$ chiều. Như trong **namespace sub2_1** trong code.
Ta sẽ cải tiến thêm độ phức tạp thời gian, bằng cách dùng cấu trúc dữ liệu segment tree, ta sẽ dùng để cải tiến đoạn duyệt từ $max(1,j-k) \to min(m,j+k)$
Vậy kết quả là $\sum_{i=1}^m dp[i]$
**Độ phức tạp:** $O(n*m*log(m))$

### Code: https://ideone.com/1OixQn