Lối đi đá (Đề tự luyện HSG Tin 9 – Bài 4)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 4 (đề tự soạn)Độ khó: KhóQuy hoạch độngĐếm số cáchTổng tiền tốĐồng dư

Đề bài

Lối đi đá. Kê $N$ phiến đá thành hàng, mỗi phiến có độ cao nguyên từ $1$ đến $K$; hai phiến liền nhau chênh lệch không quá $D$. Phiến $i$ có $a_i \ne 0$ đã kê sẵn ở độ cao $a_i$; phiến có $a_i = 0$ được tự chọn. Đếm số cách kê, lấy dư cho $10^9 + 7$.

Dữ liệu vào: dòng 1 gồm $N, K, D$ $(1 \le N, K \le 5000;\ 0 \le D < K)$; dòng 2 gồm $a_1, \dots, a_N$ $(0 \le a_i \le K)$.

Kết quả: số cách kê, lấy dư cho $10^9 + 7$.

• Subtask 1 (15%): $N \le 8$ và $K \le 6$.
• Subtask 2 (25%): $N, K \le 300$.
• Subtask 3 (20%): $D \le 3$.
• Subtask 4 (40%): không ràng buộc thêm.

Input

6 5 1
1 0 0 4 0 0

Output

8

Giải thích

Phiến 1 cao 1, phiến 4 cao 4. Tám cách: $1,2,3,4,3,x$ với $x \in \{2,3,4\}$; $1,2,3,4,4,x$ với $x \in \{3,4,5\}$; $1,2,3,4,5,x$ với $x \in \{4,5\}$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Lối đi đá

Lời mở đầu

Đây là bài đếm số cách. Điều kiện chỉ liên quan tới hai phiến liền nhau, nên khi kê lần lượt từ trái sang phải, ta chỉ cần nhớ độ cao của phiến vừa kê. Đặt

$f[i][v]$ = số cách kê các phiến $1, 2, \dots, i$ sao cho phiến $i$ cao đúng $v$.

• Phiến $1$: $f[1][v] = 1$ nếu phiến 1 chưa kê ($a_1 = 0$) hoặc $v = a_1$; ngược lại bằng $0$.
• Phiến $i \ge 2$: nếu phiến $i$ đã kê sẵn mà $v \ne a_i$ thì $f[i][v] = 0$. Ngược lại phiến $i-1$ có độ cao $u$ bất kỳ với $|u - v| \le D$, tức $u$ nằm trong đoạn $[\max(1, v-D),\ \min(K, v+D)]$, nên $f[i][v]$ = tổng các $f[i-1][u]$ trên đoạn đó.
• Đáp án $= f[N][1] + f[N][2] + \dots + f[N][K]$.

Hình 1. Mỗi ô của hàng mới bằng tổng một đoạn liên tiếp của hàng trước — chìa khoá để tăng tốc ở Cách 3.

Cách 1Thử mọi cách kê · 15%Cách 2QHĐ cộng từng ô · 60%Cách 3QHĐ + tổng tiền tố · 100%

Cách 1Thử mọi cách kê – O(K^N) · 15%

Đệ quy chọn độ cao cho từng phiến, bỏ qua lựa chọn sai với phiến kê sẵn hoặc chênh quá $D$ với phiến trước. Với $N \le 8$, $K \le 6$ có tối đa $6^8 \approx 1{,}7$ triệu cách.

#include <bits/stdc++.h>
using namespace std;
int n, K, D;
vector<int> a, h;
long long dem = 0;
// chon do cao cho phien thu i (dem tu 0)
void thu(int i) {
    if (i == n) { dem++; return; }
    for (int v = 1; v <= K; v++) {
        if (a[i] != 0 && a[i] != v) continue;             // phien da ke san
        if (i > 0 && abs(v - h[i - 1]) > D) continue;     // chenh lech qua D
        h[i] = v;
        thu(i + 1);
    }
}
int main() {
    cin >> n >> K >> D;
    a.resize(n); h.resize(n);
    for (auto &x : a) cin >> x;
    thu(0);
    cout << dem % 1000000007 << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, K, D = int(data[0]), int(data[1]), int(data[2])
    a = [int(x) for x in data[3:3 + n]]
    h = [0] * n
    dem = 0
    # duyet bang ngan xep: moi phan tu (i, v) = dang thu do cao v cho phien i
    st = [(0, 1)]
    while st:
        i, v = st.pop()
        if v > K:
            continue
        st.append((i, v + 1))                         # lan sau thu do cao v + 1
        if a[i] != 0 and a[i] != v:                   # phien da ke san
            continue
        if i > 0 and abs(v - h[i - 1]) > D:           # chenh lech qua D
            continue
        h[i] = v
        if i == n - 1:
            dem += 1
        else:
            st.append((i + 1, 1))
    print(dem % 1000000007)

main()

Không gian$O(N)$

Thời gian$O(K^N)$

Cách 2Quy hoạch động, cộng từng ô – O(N · K · D) · 60%

Cài đặt thẳng công thức ở trên: với mỗi $i$ và mỗi $v$, cộng $f[i-1][u]$ cho mọi $u$ trong đoạn. Ta chỉ cần giữ hai hàng $f$ (hàng trước) và $g$ (hàng mới). Cộng dồn bằng long long (tổng tối đa $2D + 1$ số, mỗi số nhỏ hơn $10^9 + 7$) rồi lấy dư một lần.

Độ phức tạp $O(N \cdot K \cdot D)$: với $N, K \le 300$ khoảng $2{,}7\cdot 10^7$ phép cộng; với $D \le 3$ thì dù $N = K = 5000$ cũng chỉ $1{,}75 \cdot 10^8$ phép cộng đơn giản — vẫn kịp. Cách này ăn trọn Subtask 1, 2, 3.

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    int n, K, D;
    cin >> n >> K >> D;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    // f[v] = so cach ke cac phien 1..i sao cho phien i cao v
    vector<long long> f(K + 1, 0), g(K + 1);
    for (int v = 1; v <= K; v++) f[v] = (a[1] == 0 || a[1] == v) ? 1 : 0;
    for (int i = 2; i <= n; i++) {
        for (int v = 1; v <= K; v++) {
            g[v] = 0;
            if (a[i] != 0 && a[i] != v) continue;            // phien da ke san
            for (int u = max(1, v - D); u <= min(K, v + D); u++)   // phien truoc cao u
                g[v] += f[u];
            g[v] %= MOD;
        }
        swap(f, g);
    }
    long long ans = 0;
    for (int v = 1; v <= K; v++) ans = (ans + f[v]) % MOD;
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, K, D = int(data[0]), int(data[1]), int(data[2])
    a = [0] + [int(x) for x in data[3:3 + n]]
    MOD = 1000000007
    # f[v] = so cach ke cac phien 1..i sao cho phien i cao v
    f = [0] * (K + 1)
    for v in range(1, K + 1):
        f[v] = 1 if (a[1] == 0 or a[1] == v) else 0
    for i in range(2, n + 1):
        g = [0] * (K + 1)
        for v in range(1, K + 1):
            if a[i] != 0 and a[i] != v:               # phien da ke san
                continue
            s = 0
            for u in range(max(1, v - D), min(K, v + D) + 1):   # phien truoc cao u
                s += f[u]
            g[v] = s % MOD
        f = g
    print(sum(f) % MOD)

main()

Không gian$O(K)$

Thời gian$O(N \cdot K \cdot D)$

Cách 3Tổng một đoạn = hiệu hai tổng tiền tố – O(N · K) · 100%

Khi $D$ lớn (tới $4999$), Cách 2 phải cộng hàng nghìn số cho mỗi ô. Nhưng ta luôn cộng một đoạn liên tiếp của hàng trước (Hình 1), nên chỉ cần tính trước tổng tiền tố

$P[v] = f[1] + f[2] + \dots + f[v]$ (lấy dư), khi đó tổng trên đoạn $[lo, hi]$ là $P[hi] - P[lo - 1]$.

Mỗi ô giờ chỉ tốn $O(1)$, cả bài $O(N \cdot K) = 2{,}5 \cdot 10^7$ phép tính.

Cẩn thận với phép trừ khi lấy dư

$P[hi]$ và $P[lo-1]$ đều đã lấy dư nên $P[hi] - P[lo-1]$ có thể âm; trong C++ phép % của số âm vẫn ra số âm. Phải viết (P[hi] - P[lo - 1] + MOD) % MOD. Quên cộng MOD chỉ còn 39,4% số điểm. Tương tự, nếu lưu $P$ bằng int mà không lấy dư thì tràn số — chỉ còn 19,5%.

K D Dãy a (0 = chưa kê)

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K, D;
    cin >> n >> K >> D;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    // f[v] = so cach ke cac phien 1..i sao cho phien i cao v
    vector<long long> f(K + 1, 0), P(K + 1, 0);
    for (int v = 1; v <= K; v++) f[v] = (a[1] == 0 || a[1] == v) ? 1 : 0;
    for (int i = 2; i <= n; i++) {
        for (int v = 1; v <= K; v++) P[v] = (P[v - 1] + f[v]) % MOD;     // tong tien to cua f
        for (int v = 1; v <= K; v++) {
            if (a[i] != 0 && a[i] != v) { f[v] = 0; continue; }       // phien da ke san: chi co do cao a[i]
            int lo = max(1, v - D), hi = min(K, v + D);                // phien truoc cao tu lo den hi
            f[v] = (P[hi] - P[lo - 1] + MOD) % MOD;
        }
    }
    long long ans = 0;
    for (int v = 1; v <= K; v++) ans = (ans + f[v]) % MOD;
    cout << ans << '\n';
    return 0;
}

import sys
from itertools import accumulate

def main():
    data = sys.stdin.buffer.read().split()
    n, K, D = int(data[0]), int(data[1]), int(data[2])
    a = [0] + [int(x) for x in data[3:3 + n]]
    MOD = 1000000007
    # phien truoc cua phien cao v phai cao tu lo den hi: dung P[hi] - P[lo - 1]
    HI = [v + D if v + D < K else K for v in range(1, K + 1)]
    LO = [v - D - 1 if v - D > 1 else 0 for v in range(1, K + 1)]
    # f[v] = so cach ke cac phien 1..i sao cho phien i cao v (f[0] = 0)
    f = [0] * (K + 1)
    for v in range(1, K + 1):
        f[v] = 1 if (a[1] == 0 or a[1] == v) else 0
    for i in range(2, n + 1):
        P = list(accumulate(f))                       # P[v] = f[0] + ... + f[v]
        if a[i] != 0:                                 # phien da ke san: chi co do cao a[i]
            v = a[i]
            f = [0] * (K + 1)
            f[v] = (P[HI[v - 1]] - P[LO[v - 1]]) % MOD
        else:
            f = [0]
            f += [(P[h] - P[l]) % MOD for h, l in zip(HI, LO)]
    print(sum(f) % MOD)

main()

Không gian$O(K)$

Thời gian$O(N \cdot K)$

C++▶ Chạy tay từng dòng codeMỗi phiến: tính tổng tiền tố P của hàng trước rồi lấy hiệu trên đoạn [v − D, v + D].

Dữ liệu vào (stdin) – sửa thoải mái6 5 1 1 0 0 4 0 0

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3const long long MOD = 1000000007;

4int main() {

5 ios::sync_with_stdio(false);

6 cin.tie(nullptr);

7 int n, K, D;

8 cin >> n >> K >> D;

9 vector<int> a(n + 1);

10 for (int i = 1; i <= n; i++) cin >> a[i];

11 // f[v] = so cach ke cac phien 1..i sao cho phien i cao v

12 vector<long long> f(K + 1, 0), P(K + 1, 0);

13 for (int v = 1; v <= K; v++) f[v] = (a[1] == 0 || a[1] == v) ? 1 : 0;

14 for (int i = 2; i <= n; i++) {

15 for (int v = 1; v <= K; v++) P[v] = (P[v - 1] + f[v]) % MOD; // tong tien to cua f

16 for (int v = 1; v <= K; v++) {

17 if (a[i] != 0 && a[i] != v) { f[v] = 0; continue; } // phien da ke san: chi co do cao a[i]

18 int lo = max(1, v - D), hi = min(K, v + D); // phien truoc cao tu lo den hi

19 f[v] = (P[hi] - P[lo - 1] + MOD) % MOD;

20 }

21 }

22 long long ans = 0;

23 for (int v = 1; v <= K; v++) ans = (ans + f[v]) % MOD;

24 cout << ans << '\n';

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Phiến kê sẵn KHÔNG phải "chỉ có 1 cách"

Một lỗi hay gặp: gặp phiến kê sẵn thì đặt luôn $f[i][a_i] = 1$. Nhưng số cách kê đi tới phiến đó có thể nhiều (và có thể bằng $0$ nếu phiến trước chênh quá $D$). Đúng ra vẫn phải lấy tổng trên đoạn như mọi phiến khác, chỉ là các độ cao khác $a_i$ bị gán $0$. Lỗi này chỉ còn 30,3% số điểm.

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 40 test: Subtask 1 có 11 test ($N \le 8$, $K \le 6$; gồm ví dụ, $N = K = 1$, $D = 0$, $D = K - 1$, trường hợp không thể kê), Subtask 2 có 11 test ($N, K \approx 300$; gồm "chỉ đúng một cách" và "không thể kê"), Subtask 3 có 8 test ($N, K \approx 5000$, $D \le 3$), Subtask 4 có 10 test ($N, K \approx 5000$, $D$ từ $200$ tới $4999$). Các phiến kê sẵn được lấy từ một cách kê hợp lệ (thưa, dày, hoặc sát biên $1$ / $K$). Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (11)	Sub 2 (11)	Sub 3 (8)	Sub 4 (10)	Điểm
Cách 1 – Thử mọi cách kê	Đúng 11/11	TLE 0/11	TLE 0/8	TLE 0/10	15
Cách 2 – QHĐ cộng từng ô	Đúng 11/11	Đúng 11/11	Đúng 8/8	TLE 0/10	60
Cách 3 – QHĐ + tổng tiền tố (chuẩn)	Đúng 11/11	Đúng 11/11	Đúng 8/8	Đúng 10/10	100
Sai: hiệu tổng tiền tố quên cộng MOD	Đúng 11/11	WA 5/11	WA 2/8	WA 2/10	39,4
Sai: phiến kê sẵn coi là "1 cách"	WA 6/11	WA 4/11	WA 2/8	WA 2/10	30,3
Sai: tổng tiền tố kiểu int, không lấy dư	Đúng 11/11	WA 2/11	WA 0/8	WA 0/10	19,5

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 11/11 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 29 test còn lại; Cách 2 đúng 30/30 test của ba subtask đầu (test lâu nhất khoảng 0,1 giây) và quá thời gian ở cả 10 test Subtask 4; Cách 3 đúng 40/40 test, test lâu nhất chạy khoảng 0,2 giây. Lời giải Python của Cách 3 cũng đúng 40/40 test, chạy tối đa khoảng 2,7 giây với CPython. Ví dụ của đề khá "hiền": các số rất nhỏ nên lỗi quên cộng MOD và lỗi tràn int không lộ ra, còn từ phiến 1 tới phiến 4 chỉ có đúng một cách nên lỗi "phiến kê sẵn = 1 cách" cũng vẫn ra $8$ — nhớ tự nghĩ thêm test nha!

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇