Hướng dẫn giải của seqdiv


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, dainghiajustiin, 111_LeQuangTam, hai_codeer

Hiểu bài toán

Bài toán yêu cầu đếm số lượng dãy số nguyên dương $A = (a1, a2, \dots, a_n)$ độ dài $n$ sao cho:

  1. $1 \le a_i \le K$ với mọi $i$.
  2. $a{i-1}$ chia hết cho $ai$ (tức $ai | a{i-1}$) với mọi $i > 1$.

Ta cần tính kết quả modulo $10^9 + 7$. Dựa trên các giải pháp, bài toán này là bài 'SEQDIV' với $n \le 100$ và $K$ có thể lên tới $20000$.

Các cách tiếp cận

Cách Quy hoạch động cơ bản
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n, k;
    cin >> n >> k;

    // dp[v]: số dãy độ dài i kết thúc bằng giá trị v
    vector<int> dp(k + 1, 0);
    // dp_next[v]: số dãy độ dài i+1 kết thúc bằng giá trị v
    vector<int> dp_next(k + 1, 0);

    // Khởi tạo cho độ dài 1
    for (int v = 1; v <= k; v++) {
        dp[v] = 1;
    }

    for (int i = 2; i <= n; i++) {
        fill(dp_next.begin(), dp_next.end(), 0);

        for (int u = 1; u <= k; u++) {
            if (dp[u] == 0) continue;
            // a_{i-1} = u, a_i phải là ước của u
            // Duyệt các ước của u (trừ u本身 vì có vẻ như điều kiện là chia hết? code mẫu dùng ước đúng)
            // Code mẫu dùng:
            // 1. u -> bội đúng của u (nếu điều kiện là u chia hết cho a_i)
            // 2. u -> ước đúng của u (nếu điều kiện là a_i chia hết cho u)
            // Đề bài 'a_{i-1} chia hết cho a_i' => a_i là ước của a_{i-1}.

            // Solution 1 & 3 ghi: u -> ước đúng của u
            for (int d = 1; d * d <= u; d++) {
                if (u % d == 0) {
                    int x = d;
                    // x là ước của u (a_i = x)
                    // Lưu ý: code mẫu có vẻ đang làm bài 'a_i chia hết cho a_{i-1}'? 
                    // Đọc kỹ: Solution 1 có comment '// u -> ước đúng của u' và vòng lặp d
                    // Solution 3 có comment 'DP[i][j] ... a[i] = j' và vòng lặp j la divisors of i (tên biến hơi乱)
                    // Solution 1: ndp[v] += dp[u] where v is divisor of u
                    dp_next[x] = (dp_next[x] + dp[u]) % MOD;
                    if (u / d != x) {
                        dp_next[u / d] = (dp_next[u / d] + dp[u]) % MOD;
                    }
                }
            }
            // Loại trừ chính nó nếu chỉ yêu cầu ước đúng
            // Giả sử đề bài yêu cầu a_{i-1} chia hết cho a_i (không nhất thiết phải khác)
            // Code mẫu Solution 1 không loại trừ自身 (vòng lặp d=1..sqrt, d=1 -> x=1, u/d=u -> add cả 2)
            // Solution 3 dùng dp[0] cho i-1, dp[1] cho i. Vòng lặp j la divisor of i (tên biến i là u)
            // Cần phải check lại logic: 
            // Solution 1: 
            // for (int d=1; d*d<=u; d++) {
            //   if(u%d==0) { int x=d; ndp[x] += dp[u]; if(u/d != x) ndp[u/d] += dp[u]; }
            // }
            // Vòng lặp này add dp[u] vào tất cả các ước của u.
            // Như vậy dp_next[v] có giá trị từ dp[u] với mọi u là bội của v.
        }
        swap(dp, dp_next);
    }

    long long sum = 0;
    for (int v = 1; v <= k; v++) {
        sum = (sum + dp[v]) % MOD;
    }
    cout << sum << endl;
    return 0;
}
  • Time Complexity: O(n * K * sqrt(K))
  • Space Complexity: O(K)

Đây là cách tiếp cận trực tiếp nhất. Trạng thái $dp[v]$ lưu số lượng dãy độ dài $i$ kết thúc bằng $v$. Để chuyển sang độ dài $i+1$, ta cần tính $dp{next}[v]$. Theo điều kiện $a{i-1} | ai$, nếu $ai = v$ thì $a_{i-1}$ phải là một bội của $v$.

Cách 1 (trong code): Duyệt ngược $u$ (giả sử $u$ là $a{i-1}$). Với mỗi $u$, ta cập nhật các $v$ là ước của $u$. Cụ thể, ta duyệt các ước $d$ của $u$, và cộng $dp[u]$ vào $dp{next}[d]$.

Độ phức tạp: Vòng lặp $n$ lần. Trong mỗi lần, duyệt $u$ từ $1$ đến $K$. Với mỗi $u$, ta duyệt các ước của $u$. Việc tìm ước mất $O(\sqrt{u})$. Tổng cộng là $O(n \sum_{u=1}^K \sqrt{u}) \approx O(n K^{1.5})$. Với $n=100, K=20000$, $K^{1.5} \approx 2.8 \times 10^6$, tổng $n$ lần là $2.8 \times 10^8$, khá sát nút nhưng có thể qua do thực tế $n$ nhỏ và hằng số nhỏ.

Cách Tối ưu Quy hoạch động (Duyệt bội)
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n, k;
    cin >> n >> k;

    // dp[v]: số dãy độ dài i kết thúc bằng v
    vector<int> dp(k + 1, 1); // Khởi tạo độ dài 1: mọi v đều có 1 cách

    for (int i = 2; i <= n; i++) {
        vector<int> next_dp(k + 1, 0);

        // Tính prefix sum của dp trước
        vector<int> prefix(k + 1, 0);
        for (int v = 1; v <= k; v++) {
            prefix[v] = (prefix[v - 1] + dp[v]) % MOD;
        }

        // next_dp[v] = sum(dp[u]) for all u that are multiples of v
        // next_dp[v] = sum(dp[v], dp[2v], dp[3v], ...)
        // Cach 1: Duyệt v, duyệt bội
        for (int v = 1; v <= k; v++) {
            long long sum = 0;
            for (int u = v; u <= k; u += v) {
                sum = (sum + dp[u]) % MOD;
            }
            next_dp[v] = sum;
        }

        dp = next_dp;
    }

    long long ans = 0;
    for (int v = 1; v <= k; v++) {
        ans = (ans + dp[v]) % MOD;
    }
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(n * K * log K)
  • Space Complexity: O(K)

Thay vì duyệt $u$ rồi tìm ước, ta có thể duyệt $v$ (giá trị hiện tại) và tính tổng các $dp[u]$ mà $u$ là bội của $v$.

Logic: $dp{next}[v] = \sum{m \ge 1, m \cdot v \le K} dp[m \cdot v]$.

Cách này vẫn có thể chậm nếu tính trực tiếp. Tuy nhiên, ta có thể tối ưu bằng cách sử dụng Sàng Eratosthenes hoặc các kỹ thuật tính tổng nhanh khác nếu cần, nhưng với $K=20000$, cách duyệt bội trực tiếp: Tổng số lần lặp là $\sum_{v=1}^K \frac{K}{v} \approx K \ln K$. Với $n$ bước, tổng độ phức tạp là $O(n K \ln K)$. Với $K=20000$, $K \ln K \approx 20000 \times 10 = 2 \times 10^5$. Nhân với $n=100$ được $2 \times 10^7$, rất nhanh.

Lưu ý: Code mẫu Solution 1 và Solution 3 thực chất đã sử dụng một biến thể của phương pháp này (hoặc phương pháp chia hết cho số lớn hơn). Solution 1 ghi for (int v = 2 * u; v <= k; v += u) (tìm bội đúng) và for (int d=... ) (tìm ước đúng). Dựa trên tên bài seqdiv và logic thông thường, có thể đề bài là 'ai chia hết cho a{i-1}' (tức $a{i-1}$ phải là bội của $ai$). Tuy nhiên, Solution 3 lại ghi DP[i][j] ... a[i] = j và vòng lặp LCnum = 2*num để update dp[i][num].

Giả sử đề bài là $a{i-1}$ chia hết cho $ai$ (tức $ai | a{i-1}$): $dp[i][v]$ = số dãy độ dài $i$, kết thúc bằng $v$. $dp[i][v] = \sum{u: u \text{ là bội của } v} dp[i-1][u]$. Để tính nhanh, ta có thể dùng: $dp[i][v] = \sum{m \ge 1} dp[i-1][m \cdot v]$. Đây là cách duyệt bội.

Tuy nhiên, Solution 1 có đoạn:

for (int v = 2 * u; v <= k; v += u) {
    ndp[v] = add(ndp[v], dp[u]);
}

Logic này là: Duyệt $u$ (giả sử là $a{i-1}$), cập nhật $ndp[v]$ (là $ai$) với $v$ là bội của $u$. Nếu $v$ là bội của $u$, thì $u | v$. Điều này có nghĩa là $a{i-1} | ai$. Vậy Solution 1 đang giải bài toán $a{i-1} | ai$.

Độ phức tạp của cách này (duyệt $u$, duyệt bội $v$): Tổng số lần lặp: $\sum_{u=1}^K \frac{K}{u} \approx K \ln K$. Độ phức tạp: $O(n K \ln K)$.

Đây là cách tiếp cận tối ưu và phổ biến nhất cho bài toán này với các tham số trên.

Cách Quy hoạch động dùng mảng 2 chiều (Dễ hiểu)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
int N, K;
int dp[105][20005]; // dp[i][v]: so day do dai i ket thuc bang v

int main() {
    if (fopen("SEQDIV.INP", "r")) {
        freopen("SEQDIV.INP", "r", stdin);
        freopen("SEQDIV.OUT", "w", stdout);
    }

    cin >> N >> K;

    // Khoi tao do dai 1
    for (int v = 1; v <= K; v++) dp[1][v] = 1;

    for (int i = 2; i <= N; i++) {
        // Tinh toan dp[i][v]
        // Dieu kien: a_{i-1} chia het cho a_i => a_{i-1} phai la boi cua a_i
        // dp[i][v] = sum(dp[i-1][u]) for all u that are multiples of v

        // Su dung mang tien to de tinh nhanh
        // Hoac don gian la duyet nguoc de tinh toan

        // Cach 1: Duyet v tu nho den lon, suong tien cho viec tinh tien to
        // Neu a_i = v, a_{i-1} phai la multiple of v
        // dp[i][v] = dp[i-1][v] + dp[i-1][2v] + dp[i-1][3v] + ...

        // De tinh nhanh, ta co the duyet v tu lon ve nho va cap nhat
        // Hoac su dung mang tien to

        // Solution 2 cua user dainghiajustiin co ve su dung 2 mang duyet nguoc
        // 
        // Gia su de bai la a_{i-1} | a_i
        // dp[i][v] = sum(dp[i-1][u]) where u % v == 0

        // Cach de hieu nhat: Duyet v, duyet boi
        for (int v = 1; v <= K; v++) {
            long long sum = 0;
            for (int u = v; u <= K; u += v) {
                sum += dp[i-1][u];
            }
            dp[i][v] = sum % MOD;
        }
    }

    long long ans = 0;
    for (int v = 1; v <= K; v++) ans = (ans + dp[N][v]) % MOD;
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(n * K * log K)
  • Space Complexity: O(n * K)

Sử dụng mảng 2 chiều dp[i][v] để thể hiện số dãy độ dài $i$ kết thúc bằng $v$. Logic tính toán tương tự như cách 2, nhưng cách thể hiện này trực quan hơn:

  • $dp[i][v]$ là tổng các $dp[i-1][u]$ mà $u$ là bội của $v$.
  • Công thức: $dp[i][v] = \sum_{m \ge 1} dp[i-1][m \cdot v]$.

Cách này tốn bộ nhớ $O(nK)$, nhưng với $n=100, K=20000$ thì chỉ khoảng 8MB, hoàn toàn chấp nhận được. Tuy nhiên, Solution 1 và Solution 3 (Solution 3 dùng vector<vector<int>>(2, ...) để tiết kiệm bộ nhớ) cho thấy cách tối ưu hơn về mặt bộ nhớ là chỉ cần lưu 2 mảng dpnext_dp (hoặc dp[0], dp[1]).

Tóm lại, đây là cách diễn đạt lại của cách 2, phù hợp để hiểu bài.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(n * K * sqrt(K)) O(K) Quy hoạch động cơ bản
2 O(n * K * log K) O(K) Tối ưu Quy hoạch động (Duyệt bội)
3 O(n * K * log K) O(n * K) Quy hoạch động dùng mảng 2 chiều (Dễ hiểu)

Bài học kinh nghiệm

  • Bài toán quy về bài toán quy hoạch động với state là dp[v] (số dãy kết thúc bằng v).
  • Biến đổi trạng thái phụ thuộc vào quan hệ 'chia hết'. Nếu điều kiện là $a{i-1} | ai$, thì $a{i-1}$ là bội của $ai$. Do đó, để tính $dp[i][v]$ (với $v$ là $a_i$), ta cần tổng hợp các $dp[i-1][u]$ với $u$ là bội của $v$.
  • Việc tính tổng các giá trị theo bội có thể tối ưu bằng cách duyệt theo bội (multiple looping) với độ phức tạp $O(K \log K)$ cho mỗi bước thời gian, thay vì $O(K^{1.5})$.

Lỗi thường gặp

  • Lầm tưởng về điều kiện chia hết: Cần phân biệt rõ $a{i-1} | ai$ (a{i-1} chia hết cho ai) và $ai | a{i-1}$. Hai điều kiện này dẫn đến các chuyển trạng thái ngược nhau (tìm ước vs tìm bội).
  • Sử dụng sai độ phức tạp: Tìm ước số $O(\sqrt{K})$ cho mỗi số sẽ chậm hơn đáng kể so với duyệt bội $O(K \log K)$ tổng thể.
  • Quên modulo hoặc lỗi kiểu dữ liệu khi cộng dồn.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.