Con nước (Đề tự luyện HSG Tin quốc gia – Bài 1)

Nguồn: Đề tự luyện HSG Tin học quốc gia – Bài 1 (đề tự soạn)Độ khó: KhóTổ hợpNguyên lý phản xạHệ số tam thứcQuy hoạch độngNghịch đảo modulo

Đề bài

Con nước

Thầy Sơn nuôi cá linh trong một cái đìa có cây sào khắc vạch $0, 1, \ldots, H$. Mực nước là số nguyên và phải luôn nằm trong đoạn $[1, H-1]$ (vạch $0$ là cạn đìa, vạch $H$ là tràn bờ). Mỗi giờ con nước có đúng một trong ba khả năng: nước lớn (tăng $1$ vạch), nước ròng (giảm $1$ vạch), nước đứng (giữ nguyên). Một kịch bản $N$ giờ là một dãy $N$ lựa chọn như vậy; kịch bản an toàn nếu sau mỗi giờ mực nước vẫn trong $[1, H-1]$.

Có $Q$ câu hỏi, câu hỏi thứ $i$ cho $A_i, B_i$: đếm số kịch bản an toàn bắt đầu ở vạch $A_i$ và sau đúng $N$ giờ kết thúc ở vạch $B_i$, theo modulo $10^9+7$.

Dữ liệu vào: dòng đầu $N, H, Q$ $(1 \le N \le 10^6;\ 2 \le H \le 10^6;\ 1 \le Q \le 2\cdot 10^5)$; $Q$ dòng sau mỗi dòng $A_i, B_i$ $(1 \le A_i, B_i \le H-1)$.

Kết quả: $Q$ dòng, mỗi dòng là đáp án của một câu hỏi.

Subtask 1 (20%): $N, H, Q \le 300$.
Subtask 2 (20%): $N \le 5000$ và $H > N$.
Subtask 3 (30%): $H > N$.
Subtask 4 (30%): không có ràng buộc gì thêm.

Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.

Input

3 3 2
1 1
1 2

Output

4
4

Giải thích

Chỉ có vạch $1$ và $2$ là an toàn. Ở vạch $1$ không được nước ròng, ở vạch $2$ không được nước lớn, nên mỗi giờ luôn có đúng $2$ lựa chọn: $2^3 = 8$ kịch bản, $4$ kịch bản kết thúc ở vạch $1$ và $4$ kịch bản kết thúc ở vạch $2$.

Input

Output

9
9
4

Giải thích

Câu $3$: phải giảm $3$ vạch trong $4$ giờ, tức $3$ giờ ròng và $1$ giờ đứng: $4$ cách. Câu $2$: không có bờ trên thì có $10$ kịch bản từ $2$ tới $4$, nhưng kịch bản lớn–lớn–lớn–ròng chạm vạch $5 = H$ nên bị loại, còn $9$.

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 Con nước

Lời mở đầu

Bỏ lớp áo "đìa cá" đi thì bài toán rất gọn: ta có một con trỏ trên trục số, mỗi bước nhảy $-1$, $0$ hoặc $+1$. Đếm số cách đi đúng $N$ bước từ $A$ tới $B$ mà không bao giờ chạm vạch $0$ và vạch $H$. Nếu vẽ mực nước theo thời gian, mỗi kịch bản là một đường gấp khúc nằm gọn trong "dải" giữa hai đường thẳng $y = 0$ và $y = H$:

Một kịch bản an toàn với $H = 5$, $N = 12$: đường xanh không được chạm hai đường đỏ.

Hai nhận xét sẽ dẫn đường cho cả bài:

Nếu không có bờ, số cách đi $N$ bước có tổng dịch chuyển $d$ là một con số "đẹp": hệ số của $x^{N+d}$ trong $(1 + x + x^2)^N$ (hệ số tam thức). Ta sẽ tính được cả hàng hệ số này.
Mỗi bước chỉ nhảy tối đa 1 vạch, nên muốn vượt ra ngoài dải thì đường đi bắt buộc phải chạm đúng vạch $0$ hoặc vạch $H$. Đây chính là điều kiện để dùng nguyên lý phản xạ: biến việc "đếm đường đi có chạm bờ" thành "đếm đường đi tự do từ một điểm ảnh".

Lộ trình của bài viết:

Cách 1QHĐ theo giờ · 20%Cách 2Phản xạ + tam giác hệ số · 40%Cách 3Hàng tam thức O(N) · 70%Cách 4Cộng dồn theo lớp dư · 100%

Cách 1Quy hoạch động theo từng giờ – O(Q·N·H) · 20%

Cách tự nhiên nhất: gọi $dp_t[x]$ là số kịch bản an toàn mà sau $t$ giờ mực nước đang ở vạch $x$ ($1 \le x \le H-1$). Ban đầu $dp_0[A] = 1$. Ở giờ $t$, mực nước $x$ có thể đến từ $x-1$ (nước lớn), $x$ (nước đứng) hoặc $x+1$ (nước ròng):

$$dp_t[x] = dp_{t-1}[x-1] + dp_{t-1}[x] + dp_{t-1}[x+1],$$

với quy ước $dp[0] = dp[H] = 0$ – đây chính là cách "cấm chạm bờ": mọi kịch bản đi vào vạch $0$ hay $H$ đều bị xoá khỏi bảng. Đáp án là $dp_N[B]$.

Mỗi câu hỏi tốn $O(N \cdot H)$, cả bài $O(Q \cdot N \cdot H) \approx 300^3 = 2{,}7 \cdot 10^7$ ở subtask 1 – vừa đẹp. Các em bấm thử mô phỏng dưới đây để thấy bảng được điền từng cột:

N H A

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int main() {
    int N, H, Q;
    scanf("%d %d %d", &N, &H, &Q);
    while (Q--) {
        int A, B;
        scanf("%d %d", &A, &B);
        // dp[x] = so cach de sau t gio muc nuoc dang o x (1 <= x <= H-1)
        vector<long long> dp(H + 1, 0), nd(H + 1, 0);
        dp[A] = 1;
        for (int t = 0; t < N; t++) {
            for (int x = 1; x <= H - 1; x++)
                nd[x] = (dp[x - 1] + dp[x] + dp[x + 1]) % MOD;  // dp[0] = dp[H] = 0
            swap(dp, nd);
        }
        printf("%lld\n", dp[B]);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 1000000007
    N, H, Q = int(data[0]), int(data[1]), int(data[2])
    out = []
    for q in range(Q):
        A = int(data[3 + 2 * q]); B = int(data[4 + 2 * q])
        # dp[x] = so cach de sau t gio muc nuoc dang o x (1 <= x <= H-1)
        dp = [0] * (H + 1)
        dp[A] = 1
        for t in range(N):
            nd = [0] * (H + 1)
            for x in range(1, H):
                nd[x] = (dp[x - 1] + dp[x] + dp[x + 1]) % MOD
            dp = nd
        out.append(dp[B])
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(H)$

Thời gian$O(Q \cdot N \cdot H)$

Vì sao chỉ được 20%?

Ở subtask 2 đã có $N = 5000$, $H > 5000$ và $Q = 2\cdot 10^4$: mỗi câu hỏi tốn $2{,}5\cdot 10^7$ phép tính, nhân với số câu hỏi thì vượt xa giới hạn. Phải tìm cách trả lời mỗi câu hỏi không cần mô phỏng từng giờ.

Cách 2Nguyên lý phản xạ + tam giác hệ số – O(N² + Q·N/H) · 40%

Bước 1: khi chưa có bờ

Gán cho mỗi giờ một "đơn thức": nước ròng $\to x^0$, nước đứng $\to x^1$, nước lớn $\to x^2$. Một kịch bản $N$ giờ ứng với tích $N$ đơn thức, số mũ của tích bằng $N + d$ với $d$ là tổng dịch chuyển (lớn $+1$, đứng $0$, ròng $-1$). Vậy số kịch bản không bị ràng buộc có dịch chuyển đúng $d$ là

$$T(d) = [x^{N+d}]\,(1 + x + x^2)^N = a_{N+d},$$

trong đó $a_0, a_1, \ldots, a_{2N}$ là các hệ số của $(1+x+x^2)^N$ (gọi là hệ số tam thức). Ví dụ $N = 3$: $(1+x+x^2)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6$, nên có $7$ kịch bản 3 giờ quay về đúng mực cũ, $6$ kịch bản lên 1 vạch, ...

Ở Cách 2 ta tính hàng $a$ bằng cách nhân dần $N$ lần với $(1+x+x^2)$, giống tam giác Pascal nhưng mỗi ô bằng tổng 3 ô phía trên: $O(N^2)$, đủ nhanh với $N \le 5000$.

Bước 2: một bờ – phép phản xạ

Tạm quên bờ trên, chỉ có bờ dưới vạch $0$. Xét một đường đi từ $A$ tới $B$ có chạm vạch $0$, gọi $\tau$ là lần chạm đầu tiên. Lật đối xứng (qua vạch $0$) phần đường đi từ đầu đến $\tau$, phần sau giữ nguyên: ta được một đường đi từ $-A$ tới $B$. Ngược lại, mọi đường từ $-A$ (âm) tới $B$ (dương) đều phải cắt vạch $0$ – và vì mỗi bước chỉ nhảy tối đa 1 nên nó chạm đúng vạch 0 – lật lại phần đầu ta được đường từ $A$ có chạm $0$. Đây là song ánh, nên

$$\#\{\text{đường } A \to B \text{ có chạm } 0\} = \#\{\text{đường tự do } -A \to B\} = T(B + A).$$

Phép phản xạ: mỗi đường "phạm luật" ứng đúng với một đường tự do xuất phát từ điểm ảnh $-A$.

Vậy với một bờ: số đường an toàn $= T(B - A) - T(B + A)$. Nhờ các bước $\{-1, 0, +1\}$ đối xứng nên phép lật vẫn biến một kịch bản hợp lệ thành một kịch bản hợp lệ – bước "nước đứng" không làm hỏng gì cả.

Bước 3: hai bờ – phản xạ luân phiên vô hạn lần

Có cả bờ trên $H$ thì ta trừ $T(\ldots)$ của ảnh qua vạch $0$ và ảnh qua vạch $H$; nhưng những đường chạm cả hai bờ lại bị trừ hai lần, nên phải cộng lại (ảnh của ảnh), rồi lại trừ ảnh của ảnh của ảnh... Đây là bao hàm – loại trừ theo dãy các lần chạm bờ luân phiên. Mỗi lần phản xạ qua vạch $0$ biến $y \mapsto -y$, qua vạch $H$ biến $y \mapsto 2H - y$; hợp của hai phép là tịnh tiến $2H$. Cuối cùng các "điểm ảnh" của $B$ (nhìn từ $A$) là $B + 2kH$ (dấu $+$) và $-B + 2kH$ (dấu $-$) với mọi số nguyên $k$:

$$\boxed{\ \text{Đáp án}(A, B) = \sum_{k \in \mathbb{Z}} \Big[\, T(B - A + 2kH) - T(-B - A + 2kH) \,\Big]\ }$$

Tổng này thực chất hữu hạn: $T(d) = 0$ khi $|d| > N$, nên chỉ có khoảng $N/H + 1$ giá trị $k$ cho mỗi loại. Trong subtask 2 và 3 có $H > N$, nên chỉ còn vài số hạng ($k \in \{-1, 0, 1\}$). Mô phỏng dưới đây liệt kê từng số hạng và đối chiếu với QHĐ của Cách 1:

N H A B

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int N, H, Q;
vector<long long> a;   // a[j] = he so x^j cua (1+x+x^2)^N

long long T(long long d) {           // so day dich chuyen tong cong d (khong ran buoc)
    if (d < -N || d > N) return 0;
    return a[N + d];
}

int main() {
    scanf("%d %d %d", &N, &H, &Q);
    a.assign(2 * N + 1, 0);
    a[0] = 1;
    for (int t = 1; t <= N; t++) {          // nhan them (1 + x + x^2), tam giac Pascal 3 nhanh
        vector<long long> b(2 * N + 1, 0);
        for (int j = 0; j <= 2 * t; j++) {
            long long v = a[j];
            if (j >= 1) v += a[j - 1];
            if (j >= 2) v += a[j - 2];
            b[j] = v % MOD;
        }
        a = b;
    }
    while (Q--) {
        int A, B;
        scanf("%d %d", &A, &B);
        long long ans = 0;
        long long K = N / (2LL * H) + 2;
        for (long long k = -K; k <= K; k++) {
            ans += T(B - A + 2 * k * H);
            ans -= T(-B - A + 2 * k * H);
        }
        ans %= MOD; if (ans < 0) ans += MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 1000000007
    N, H, Q = int(data[0]), int(data[1]), int(data[2])
    a = [1]
    for t in range(N):                      # nhan them (1 + x + x^2)
        b = [0] * (len(a) + 2)
        for j, v in enumerate(a):
            b[j] += v; b[j + 1] += v; b[j + 2] += v
        a = [v % MOD for v in b]
    out = []
    K = N // (2 * H) + 2
    for q in range(Q):
        A = int(data[3 + 2 * q]); B = int(data[4 + 2 * q])
        ans = 0
        for k in range(-K, K + 1):
            d = B - A + 2 * k * H
            if -N <= d <= N: ans += a[N + d]
            d = -B - A + 2 * k * H
            if -N <= d <= N: ans -= a[N + d]
        out.append(ans % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N^2 + Q \cdot (N/H + 1))$

Bẫy "chỉ phản xạ một lần"

Nhiều bạn chỉ trừ hai ảnh $T(B+A)$ và $T(2H - A - B)$ rồi dừng. Công thức đó đúng khi $H > N$ (không đường nào kịp chạm cả hai bờ), nên vẫn ăn trọn subtask 2 và 3 – nhưng sai ngay khi dải hẹp. Bộ test bắt lỗi này ở subtask 1 và 4 (xem bảng cuối bài).

Cách 3Tính cả hàng hệ số tam thức trong O(N) · 70%

Với $N = 10^6$ thì tam giác $O(N^2)$ là không thể. Hệ số tam thức không có công thức đóng gọn như $\binom{N}{k}$, nhưng có một công thức truy hồi rất đẹp nhờ đạo hàm. Đặt $P(x) = (1 + x + x^2)^N = \sum_j a_j x^j$. Đạo hàm:

$$P'(x) = N (1 + 2x)(1 + x + x^2)^{N-1} \;\Longrightarrow\; (1 + x + x^2)\,P'(x) = N(1 + 2x)\,P(x).$$

So sánh hệ số của $x^j$ hai vế: vế trái là $(j+1)a_{j+1} + j\,a_j + (j-1)a_{j-1}$, vế phải là $N a_j + 2N a_{j-1}$. Chuyển vế:

$$\boxed{\ a_{j+1} = \dfrac{(N - j)\,a_j + (2N - j + 1)\,a_{j-1}}{j + 1}\ },\qquad a_0 = 1,\ a_1 = N.$$

Kiểm tra với $N = 3$: $a_2 = \frac{2 \cdot 3 + 6 \cdot 1}{2} = 6$, $a_3 = \frac{1 \cdot 6 + 5 \cdot 3}{3} = 7$ – khớp với hàng $1, 3, 6, 7, 6, 3, 1$ ở trên.

Ba chi tiết kỹ thuật:

Phép chia cho $j+1$ trong modulo $p = 10^9+7$ (nguyên tố, lớn hơn $2N$) đổi thành nhân với nghịch đảo. Tính mọi nghịch đảo $1..N+1$ trong $O(N)$ bằng công thức quen thuộc $\text{inv}[i] = -\lfloor p/i \rfloor \cdot \text{inv}[p \bmod i] \pmod p$.
Đối xứng: $a_j = a_{2N-j}$ (đổi nước lớn ↔ nước ròng). Chỉ cần truy hồi tới $j = N$, nửa còn lại chép đối xứng. Nhờ vậy hệ số $(N - j)$ luôn dương, không lo số âm.
Tràn số: $(2N - j + 1) \cdot a_{j-1}$ có thể tới $2\cdot 10^6 \cdot 10^9$ – phải dùng long long. Lời giải wrong_tranint.cpp quên chỗ này và chỉ được vài test nhỏ.

Mỗi câu hỏi vẫn duyệt các số hạng $k$ như Cách 2:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int N, H, Q;
vector<long long> a;   // a[j] = he so x^j cua (1+x+x^2)^N

long long T(long long d) {
    if (d < -N || d > N) return 0;
    return a[N + d];
}

int main() {
    scanf("%d %d %d", &N, &H, &Q);
    vector<long long> inv(N + 2, 1);
    for (int i = 2; i <= N + 1; i++) inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
    a.assign(2 * N + 1, 0);
    a[0] = 1; a[1] = N % MOD;
    for (int j = 1; j < N; j++)
        a[j + 1] = ((N - j) * a[j] + (2LL * N - j + 1) % MOD * a[j - 1]) % MOD * inv[j + 1] % MOD;
    for (int j = 0; j < N; j++) a[2 * N - j] = a[j];
    while (Q--) {
        int A, B;
        scanf("%d %d", &A, &B);
        long long ans = 0;
        long long K = N / (2LL * H) + 2;
        for (long long k = -K; k <= K; k++) {
            ans += T(B - A + 2 * k * H);
            ans -= T(-B - A + 2 * k * H);
        }
        ans %= MOD; if (ans < 0) ans += MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 1000000007
    N, H, Q = int(data[0]), int(data[1]), int(data[2])
    inv = [1] * (N + 2)
    for i in range(2, N + 2):
        inv[i] = (MOD - (MOD // i) * inv[MOD % i] % MOD) % MOD
    a = [0] * (2 * N + 1)
    a[0] = 1
    a[1] = N % MOD
    for j in range(1, N):
        a[j + 1] = ((N - j) * a[j] + (2 * N - j + 1) * a[j - 1]) % MOD * inv[j + 1] % MOD
    for j in range(N):
        a[2 * N - j] = a[j]
    out = []
    K = N // (2 * H) + 2
    for q in range(Q):
        A = int(data[3 + 2 * q]); B = int(data[4 + 2 * q])
        ans = 0
        for k in range(-K, K + 1):
            d = B - A + 2 * k * H
            if -N <= d <= N: ans += a[N + d]
            d = -B - A + 2 * k * H
            if -N <= d <= N: ans -= a[N + d]
        out.append(ans % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N + Q \cdot (N/H + 1))$

Nút thắt cuối cùng

Khi dải hẹp, ví dụ $H = 2$, mỗi câu hỏi có tới khoảng $2N/H = 10^6$ số hạng; với $Q = 2\cdot 10^5$ câu hỏi là $10^{11}$ phép tính. Ngay cả $H = 600$ cũng còn $\approx 3300$ số hạng mỗi câu, chạy mất hơn 8 giây. Cần trả lời mỗi câu hỏi trong $O(1)$.

Cách 4Cộng dồn theo lớp đồng dư 2H – O(N + Q) · 100%

Nhìn kỹ tổng $\sum_k T(d + 2kH) = \sum_k a_{N + d + 2kH}$: các chỉ số $N + d + 2kH$ lập thành một cấp số cộng công sai $2H$, và ta lấy mọi phần tử của nó nằm trong $[0, 2N]$. Nói cách khác, đó là tổng các $a_i$ với $i \in [0, 2N]$ và $i \equiv N + d \pmod{2H}$ – tổng của cả một lớp đồng dư.

Vậy ta chuẩn bị mảng cộng dồn "nhảy cóc" bước $2H$:

$$P_i = a_i + P_{i - 2H}\quad (P_i = a_i \text{ nếu } i < 2H).$$

$P_i$ là tổng $a_i + a_{i-2H} + a_{i-4H} + \ldots$ Với một $d$, đặt $r = (N + d) \bmod 2H$ (lấy số dư không âm). Nếu $r > 2N$ thì lớp này không có phần tử nào, tổng bằng $0$; ngược lại phần tử lớn nhất của lớp trong $[0, 2N]$ là $i^* = r + 2H \cdot \lfloor (2N - r) / 2H \rfloor$ và

$$F(d) = \sum_k T(d + 2kH) = P_{i^*},\qquad \text{Đáp án}(A, B) = F(B - A) - F(-A - B).$$

Ví dụ $N = 4$, $H = 2$ (chỉ có vạch $1$), $A = B = 1$: hàng $a = 1, 4, 10, 16, 19, 16, 10, 4, 1$. $F(0)$: $r = 4 \bmod 4 = 0$, lớp gồm chỉ số $0, 4, 8$, tổng $1 + 19 + 1 = 21$. $F(-2)$: $r = 2$, lớp gồm $2, 6$, tổng $10 + 10 = 20$. Đáp án $21 - 20 = 1$ – đúng, vì chỉ có kịch bản "đứng – đứng – đứng – đứng".

Cẩn thận số dư âm trong C++

$N + d$ có thể âm (ví dụ $d = -A - B$ khi $A + B > N$). Trong C++, (-7) % 4 == -3, nên phải viết ((x % m) + m) % m. Có bạn "chữa cháy" bằng cách trả về $0$ khi $N + d < 0$ – sai, vì các chỉ số $N + d + 2kH$ với $k > 0$ vẫn có thể rơi vào $[0, 2N]$. Lời giải wrong_amdu.cpp mắc lỗi này và mất trắng subtask 2, 3.

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int N, H, Q;
vector<long long> a, P;   // a[j] = he so x^j cua (1+x+x^2)^N ; P = tong theo lop du 2H

long long F(long long d) {           // tong a[N + d + 2kH] tren moi k
    long long r = ((N + d) % (2LL * H) + 2LL * H) % (2LL * H);
    if (r > 2LL * N) return 0;
    long long i = r + 2LL * H * ((2LL * N - r) / (2LL * H));
    return P[i];
}

int main() {
    scanf("%d %d %d", &N, &H, &Q);
    vector<long long> inv(N + 2, 1);
    for (int i = 2; i <= N + 1; i++) inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
    a.assign(2 * N + 1, 0);
    a[0] = 1; a[1] = N % MOD;
    for (int j = 1; j < N; j++)
        a[j + 1] = ((N - j) * a[j] + (2LL * N - j + 1) % MOD * a[j - 1]) % MOD * inv[j + 1] % MOD;
    for (int j = 0; j < N; j++) a[2 * N - j] = a[j];
    P.assign(2 * N + 1, 0);
    for (int i = 0; i <= 2 * N; i++) {
        P[i] = a[i];
        if (i >= 2 * H) P[i] = (P[i] + P[i - 2 * H]) % MOD;
    }
    string out;
    for (int q = 0; q < Q; q++) {
        int A, B;
        scanf("%d %d", &A, &B);
        long long ans = (F(B - A) - F(-A - B) + MOD) % MOD;
        out += to_string(ans);
        out += '\n';
    }
    fputs(out.c_str(), stdout);
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 1000000007
    N, H, Q = int(data[0]), int(data[1]), int(data[2])
    inv = [1] * (N + 2)
    for i in range(2, N + 2):
        inv[i] = (MOD - (MOD // i) * inv[MOD % i] % MOD) % MOD
    a = [0] * (2 * N + 1)
    a[0] = 1
    a[1] = N % MOD
    for j in range(1, N):
        a[j + 1] = ((N - j) * a[j] + (2 * N - j + 1) * a[j - 1]) % MOD * inv[j + 1] % MOD
    for j in range(N):
        a[2 * N - j] = a[j]
    # P[i] = a[i] + a[i - 2H] + a[i - 4H] + ...
    W = 2 * H
    P = a[:W]
    for s in range(W, 2 * N + 1, W):
        blk = a[s:s + W]
        prev = P[s - W:s - W + len(blk)]
        P.extend([(x + y) % MOD for x, y in zip(blk, prev)])
    LIM = 2 * N
    out = []
    for q in range(Q):
        A = int(data[3 + 2 * q]); B = int(data[4 + 2 * q])
        # F(B - A)
        r = (N + B - A) % W
        f1 = P[r + W * ((LIM - r) // W)] if r <= LIM else 0
        r = (N - A - B) % W
        f2 = P[r + W * ((LIM - r) // W)] if r <= LIM else 0
        out.append((f1 - f2) % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N + Q)$

C++▶ Chạy tay từng dòng codeTheo dõi hàng hệ số a, mảng cộng dồn P và từng lần gọi F(d).

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

Dữ liệu mẫu:

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

2using namespace std;

3const long long MOD = 1000000007LL;

4int N, H, Q;

5vector<long long> a, P; // a[j] = he so x^j cua (1+x+x^2)^N ; P = tong theo lop du 2H

7long long F(long long d) { // tong a[N + d + 2kH] tren moi k

8 long long r = ((N + d) % (2LL * H) + 2LL * H) % (2LL * H);

9 if (r > 2LL * N) return 0;

10 long long i = r + 2LL * H * ((2LL * N - r) / (2LL * H));

11 return P[i];

12}

14int main() {

15 scanf("%d %d %d", &N, &H, &Q);

16 vector<long long> inv(N + 2, 1);

17 for (int i = 2; i <= N + 1; i++) inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;

18 a.assign(2 * N + 1, 0);

19 a[0] = 1; a[1] = N % MOD;

20 for (int j = 1; j < N; j++)

21 a[j + 1] = ((N - j) * a[j] + (2LL * N - j + 1) % MOD * a[j - 1]) % MOD * inv[j + 1] % MOD;

22 for (int j = 0; j < N; j++) a[2 * N - j] = a[j];

23 P.assign(2 * N + 1, 0);

24 for (int i = 0; i <= 2 * N; i++) {

25 P[i] = a[i];

26 if (i >= 2 * H) P[i] = (P[i] + P[i - 2 * H]) % MOD;

27 }

28 string out;

29 for (int q = 0; q < Q; q++) {

30 int A, B;

31 scanf("%d %d", &A, &B);

32 long long ans = (F(B - A) - F(-A - B) + MOD) % MOD;

33 out += to_string(ans);

34 out += '\n';

35 }

36 fputs(out.c_str(), stdout);

37 return 0;

38}

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

Bộ test có 33 test: subtask 1 (9 test, $N, H, Q \le 300$), subtask 2 (8 test, $N \approx 5000$, $H > N$, $Q = 2\cdot 10^4$), subtask 3 (8 test, $N \approx 10^6$, $H > N$), subtask 4 (8 test, $N \approx 10^6$, $Q = 2\cdot 10^5$, $H \in \{2, 3, 97, 256, 350, 420, 512, 600\}$). Điểm chấm kiểu "Tổng": đúng test nào được điểm test đó.

Cách làm	Sub 1 (20%)	Sub 2 (20%)	Sub 3 (30%)	Sub 4 (30%)	Điểm
Cách 1 – QHĐ theo giờ	Đúng	TLE	TLE	TLE	20
Cách 2 – Phản xạ + tam giác O(N²)	Đúng	Đúng	TLE	TLE	40
Cách 3 – Hàng tam thức O(N), duyệt từng số hạng	Đúng	Đúng	Đúng	TLE	70
Cách 4 – Cộng dồn theo lớp dư (sol.cpp)	Đúng	Đúng	Đúng	Đúng	100
Sai: chỉ phản xạ 1 lần qua mỗi bờ	5/9 (WA)	Đúng	Đúng	WA	61,1
Sai: trả 0 khi N + d < 0 (xử lý số dư âm sai)	6/9 (WA)	WA	WA	Đúng	43,3
Sai: quên long long trong truy hồi	2/9 (WA)	WA	WA	WA	4,4
Sai: cho phép chạm vạch 0 và vạch H	1/9 (WA)	WA	WA	WA	2,2

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: sub1.cpp được 20 điểm; sub2.cpp được 40 điểm; sub3.cpp được 70 điểm; sol.cpp được 100 điểm; wrong_motlan.cpp được 61,1 điểm; wrong_amdu.cpp được 43,3 điểm; wrong_tranint.cpp được 4,4 điểm; wrong_chambo.cpp được 2,2 điểm. Lời giải chuẩn sol.cpp chạy test lâu nhất hết 0,3 giây, bản Python sol.py cho cùng đáp án trên mọi test (CPython lâu nhất 4,5 giây, PyPy nhanh hơn nhiều). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian.

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 😇

Lập Trình Thuật Toán

Con nước (Đề tự luyện HSG Tin quốc gia – Bài 1)

Đề bài

Lời mở đầu

Cách 1Quy hoạch động theo từng giờ – O(Q·N·H) · 20%

Cách 2Nguyên lý phản xạ + tam giác hệ số – O(N² + Q·N/H) · 40%

Bước 1: khi chưa có bờ

Bước 2: một bờ – phép phản xạ

Bước 3: hai bờ – phản xạ luân phiên vô hạn lần

Cách 3Tính cả hàng hệ số tam thức trong O(N) · 70%

Cách 4Cộng dồn theo lớp đồng dư 2H – O(N + Q) · 100%

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

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++