Hướng dẫn cho LQDOJ CUP 2022 - Round 5 - BITSTR

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: nhphucqt, ldn694

Subtask $1$ ($20\%$ số điểm): $n \leq 20$.

Tutorial

Sử dụng thuật toán duyệt DFS hoặc BFS để duyệt đến hết tất cả các trạng thái, với mỗi trạng thái $\texttt{mask}$, có $n-u+1$ cách chuyển trạng thái bằng thao tác $1$, có $n - v + 1$ cách chuyển trạng thái bằng thao tác $2$.
Độ phức tạp: $\mathcal{O}(T\times 2^n\times n)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 20;

int n, u, v;
bool mark[1 << MAX_N];
int q[1 << MAX_N];
int mask1[MAX_N], mask0[MAX_N];
int ans[MAX_N + 1][MAX_N + 1][MAX_N + 1];

void bfs() {
    for (int i = n - u; i >= 0; --i) {
        mask0[i] = (~(((1 << u) - 1) << i));
    }
    for (int i = n - v; i >= 0; --i) {
        mask1[i] = (((1 << v) - 1) << i);
    }

    memset(mark, true, (1 << n) * sizeof(bool));
    int left = 0, right = 0;
    q[right++] = 0;
    mark[0] = false;
    int x, y;
    while (left < right) {
        x = q[left++];
        for (int i = n - u; i >= 0; --i) {
            y = x & mask0[i];
            if (mark[y]) {
                mark[y] = 0;
                q[right++] = y;
            }
        }
        for (int i = n - v; i >= 0; --i) {
            y = x | mask1[i];
            if (mark[y]) {
                mark[y] = 0;
                q[right++] = y;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("BITSTR.inp", "r", stdin);
    freopen("BITSTR.out", "w", stdout);

    int nTest;
    cin >> nTest;

    memset(ans, -1, sizeof (ans));
    while (nTest--) {
        cin >> n;
        cin >> u >> v;
        if (ans[n][u][v] != -1) {
            cout << ans[n][u][v] << '\n';
        } else {
            bfs();
            int res = 0;
            for (int mask = (1 << n) - 1; mask >= 0; --mask) {
                res += mark[mask];
            }
            ans[n][u][v] = (1 << n) - res;
            cout << ans[n][u][v] << '\n';
        }
    }

    return 0;
}

Subtask $2$ ($20\%$ số điểm): $u = n$.

Tutorial

Nhận xét rằng vì $u = n$ nên thao tác $\texttt{1}$ không có ý nghĩa gì cả, như vậy ta sẽ chỉ xét thao tác $\texttt{2}$. Dễ nhận thấy rằng các với dãy nhị phân có các đoạn bit $1$ liên tiếp đều có độ dài $\geq v$, ta có thể thực hiện thao tác $\texttt{2}$ để tạo ra được các dãy nhị phân đó từ dãy nhị phân ban đầu. Ngược lại nếu trong dãy nhị phân tồn tại một đoạn bit $1$ liên tiếp có độ dài $< v$ thì rõ ràng không thể nào tạo ra được dãy nhị phân đó từ dãy ban đầu được.
Từ đó, để giải quyết được subtask này, ta cần đếm số lượng dãy nhị phân thoả mãn tất cả các đoạn bit $1$ đều có độ dài $\geq v$.
Bài toán này có thể được giải quyết bằng quy hoạch động.
Gọi $\texttt{dp}[i][j]$ là số lượng dãy nhị phân độ dài $i$ thoả mãn các đoạn bit $1$ (ngoại trừ đoạn bit $1$ ở cuối nếu có) đều có độ dài $\geq v$ và $j$ là số lượng bit $1$ ở cuối ($j = 0$ nếu bit cuối là $0$).
Công thức truy hồi:
$$\begin{split} & \texttt{dp}[0][0] = 1\\ \\ & \texttt{dp}[i][j] = \begin{cases} \texttt{dp}[i-1][j-1] &, \ \text{if } j > 0\\ \texttt{dp}[i-1][0] + \displaystyle\sum_{k=v}^{i-1}{\texttt{dp}[i-1][k]} &, \ \text{if } j = 0 \end{cases} \ \ \ \ \ i = \overline{1..n} \ , \ j = \overline{0..i} \end{split}$$
Kết quả chính là $\texttt{dp}[n][0] + \displaystyle\sum_{i=v}^{n}{\texttt{dp}[n][i]}$
Độ phức tạp: $\mathcal{O}(T \times n^2)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2005;
const int MOD = 1e9 + 7;

int numTest;
int n, v, u;
int dp[MAX_N][MAX_N];

inline int add(int x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
    return x;
}

inline void selfAdd(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

inline int mul(long long x, int y) {
    return x * y % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("BITSTR.inp", "r", stdin);
    freopen("BITSTR.out", "w", stdout);

    cin >> numTest;
    while (numTest--) {
        cin >> n;
        cin >> u >> v;
        assert(u == n);

        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i - 1][0];
            for (int k = v; k < i; ++k) {
                selfAdd(dp[i][0], dp[i - 1][k]);
            }
            for (int j = 1; j <= i; ++j) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }

        int res = dp[n][0];
        for (int j = v; j <= n; ++j) {
            selfAdd(res, dp[n][j]);
        }

        cout << res << '\n';
    }

    return 0;
}

Subtask $3$ ($20\%$ số điểm): $n \leq 40$.

Tutorial

Kể từ subtask này, tức là subtask $\texttt{3}$, $\texttt{4}$, $\texttt{5}$ đều được giải dựa trên một ý tưởng chung.
Thay vì đếm số lượng dãy nhị phân có thể tạo ra được từ dãy nhị phân ban đầu, ta sẽ tính số lượng dãy nhị phân mà tồn tại cách thực hiện ngược lại thao tác $\texttt{1}$ và $\texttt{2}$ sao cho nhận lại được dãy ban đầu. Tức là,

Nếu trong dãy có một đoạn bit $1$ nào đó có độ dài $\geq v$, ta có thể chuyển đoạn đó về đoạn bit $0$ bằng cách thực hiện ngược lại một hay nhiều thao tác $\texttt{2}$ phủ lên đoạn bit đó.
Nếu trong dãy có một đoạn bit $0$ nào đó có độ dài $\geq u$, ta có thể chuyển đoạn đó về đoạn bit $1$ bằng cách thực hiện ngược lại một hay nhiều thao tác $\texttt{1}$ phủ lên đoạn bit đó.

Nếu có thể bằng một cách nào đó chuyển một dãy nhị phân về được dãy nhị phân ban đầu, thì cũng từ dãy nhị phân ban đầu có thể thực hiện hai thao tác $\texttt{1}$ và $\texttt{2}$ để chuyển về lại dãy nhị phân đó. nếu không tồn tại cách chuyển về dãy nhị phân ban đầu thì dãy nhị phân đó không thoả mãn.
Ví dụ, với $n = 9$, $u = 5$, $v = 3$, xét dãy nhị phân sau $\texttt{110111101}$:

Nhận thấy đoạn $[4,7]$ là đoạn bit $1$ độ dài $4 \geq v$, vì vậy có thể chuyển đoạn đó về đoạn bit $0$, dãy nhị phân trở thành $\texttt{110000001}$.
Nhận thấy đoạn $[3,8]$ là đoạn bit $0$ độ dài $6 \geq u$, vì vậy có thể chuyển đoạn đó về đoạn bit $1$, dãy nhị phân trở thành $\texttt{111111111}$.
Nhận thấy đoạn $[1,9]$ là đoạn bit $1$ độ dài $9 \geq v$, vì vậy có thể chuyển đoạn đó về đoạn bit $0$, dãy nhị phân trở thành $\texttt{000000000}$.

Từ đây kết luận được là $\texttt{110111101}$ là một dãy nhị phân thoả mãn.
Từ đó xây dựng được một cách kiểm tra đoạn có thoả mãn hay không (giả sử $u \geq v$):

Một dãy nhị phân thoả mãn khi trong quá trình thực hiện ngược lại thao tác, ta luôn có thể chuyển các đoạn bit $0$ thành đoạn bit $1$ và ngược lại.
Nếu tồn tại một đoạn bit $0$ có độ dài $\geq u$ thì dãy nhị phân đó thoả mãn. Bởi vì khi đó khi chuyển đoạn bit $0$ đó thành đoạn bit $1$, nó sẽ hợp với các đoạn bit $1$ bên cạnh thành đoạn bit $1$ có độ dài $\geq u \geq v$. Cứ như vậy sẽ thoả mãn được điều kiện $\texttt{1}$.
Nếu không tồn tại, kiểm tra xem liệu có tồn tại một đoạn bit $1$ có độ dài $\geq v$, nếu không tồn tại thì dãy không thoả mãn. Nếu tồn tại, chuyển hết tất cả các đoạn bit $1$ có độ dài $\geq v$ thành đoạn bit $0$ rồi kiểm tra lại điều kiện $\texttt{2}$. Nếu lần này đoạn xuất hiện một đoạn bit $0$ thoả mãn thì dãy nhị phân đó thoả mãn, ngược lại thì dãy không thoả mãn.

Từ cách kiểm tra trên ta sẽ rút gọn lại cách giải bài toán như sau:
Đếm số lượng dãy nhị phân thoả mãn tính chất đó là tồn tại một đoạn bit gồm các bit $\bf{0}$ và các đoạn bit $\bf{1}$ có độ dài $\bf{\geq v}$ có độ dài $\bf{\geq u}$.
Xét lại ví dụ ở trên, với $n = 9$, $u = 5$, $v = 3$, kiểm tra liệu dãy nhị phân $\texttt{110111101}$ có thoả mãn hay không, ta nhận thấy rằng đoạn $[3,8]$ là đoạn chứa các bit $0$ và đoạn bit $1$ (đoạn $[4,7]$) có độ dài là $4 \geq v$, và đoạn $[3,8]$ có độ dài $6 \geq u$. Vậy nên dãy $\texttt{110111101}$ là một dãy nhị phân thoả mãn.
Đồng thời để đơn giản hoá việc cài đặt, ta cần nhận xét thêm một tính chất, đó là khi đảo hai giá trị $u$ và $v$ thì kết quả bài toán vẫn giữ nguyên, điều này khá dễ thấy vì $u$ và $v$ có vai trò như nhau, bất kỳ một cách tạo ra một dãy nhị phân thì khi đảo giá trị $u$ và $v$ lại thì dãy nhị phân đó sẽ bị đảo ngược lại (tức là bit $0$ thành bit $1$, bit $1$ thành bit 0).
Vì vậy nếu gặp bài toán mà $u < v$, ta có thể đảo hai giá trị $u$ và $v$ để $u \geq v$. Thống nhất một cách kiểm tra và tính toán.
Để đếm được số lượng dãy nhị phân thoả mãn tính chất nói trên (phần in đậm), ta có thể sử dụng quy hoạch động:
Kể từ giờ, ta gọi một đoạn bit thoả mãn là một đoạn bit chứa các bit $0$ và các đoạn bit $1$ có độ dài $\geq v$ có độ dài $\geq u$. Một dãy nhị phân thoả mãn là một dãy nhị phân chứa ít nhất một đoạn bit thoả mãn.
Gọi $\texttt{dp}[i][j][k][t]$ là số lượng dãy nhị phân với:

$i$ là độ dài của dãy nhị phân,
$j$ là đoạn bit thoả mãn dài nhất (không tính đoạn bit thoả mãn dài nhất ở cuối được phép chứa đoạn bit $1$ độ dài $< v$ ở cuối nếu có),
$k$ là độ dài đoạn bit thoả mãn dài nhất ở cuối (cho phép chứa đoạn bit $1$ độ dài $< v$ ở cuối nếu có),
$t$ là số lượng bit $1$ ở cuối ($t = 0$ nếu không bit cuối là $0$).

Khởi tạo $\texttt{dp}[i][j][k][t] = 0, \ \texttt{dp}[0][0][0][0] = 1$
Ta sẽ tiến hành cập nhật các giá trị khác từ $\texttt{dp}[i][j][k][t]$ thông qua đoạn code này:

code

C++

memset(dp, 0, sizeof dp);
dp[0][0][0][0] = 1;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
        for (int k = 0; k+j <= i; ++k) {
            for (int t = 0; t <= k; ++t) { 
                if (dp[i][j][k][t] == 0) {
                    continue;
                }
                // Gán bit thứ i+1 = 0
                if (t > 0 && t < v) {
                    dp[i+1][max(j,k-t)][1][0] += dp[i][j][k][t];
                } 
                else {
                    dp[i+1][j][k+1][0] += dp[i][j][k][t];
                }
                // Gán bit thứ i+1 = 1
                dp[i+1][j][k+1][t+1] += dp[i][j][k][t];
            }
        }
    }
}

Lưu ý

Các code được viết trong lời giải là để đọc hiểu thuật toán nên không có phép mod như trong đề bài.

Sau khi tính xong mảng $\texttt{dp}$, ta sẽ tính kết quả bài toán thông qua đoạn code sau:

code

C++

int res = 0;
for (int j = 0; j <= n; ++j) {
    for (int k = 0; k+j <= n; ++k) {
    for (int t = 0; t <= k; ++t) {
        int maxs = t < v ? max(j, k-t) : max(j, k);
        if (maxs >= u) {
            res += dp[n][j][k][t];
        }
    }
    }
}

Độ phức tạp: $\mathcal{O}(T \times n^4)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 47;
const int MOD = 1e9 + 7;

int numTest;
int n, u, v;
int dp[MAX_N][MAX_N][MAX_N][MAX_N];

inline int add(int x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
    return x;
}

inline void selfAdd(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

inline int mul(long long x, int y) {
    return x * y % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("BITSTR.inp", "r", stdin);
    freopen("BITSTR.out", "w", stdout);

    cin >> numTest;

    while (numTest--) {
        cin >> n;
        cin >> u >> v;
        if (u < v) {
            swap(u, v);
        }

        memset(dp, 0, sizeof(dp));
        dp[0][0][0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int k = 0; k + j <= i; ++k) {
                    for (int t = 0; t <= k; ++t) {
                        if (dp[i][j][k][t] == 0) {
                            continue;
                        }
                        // Gán bit thứ i+1 = 0
                        if (t > 0 && t < v) {
                            selfAdd(dp[i + 1][max(j, k - t)][1][0], dp[i][j][k][t]);
                        } else {
                            selfAdd(dp[i + 1][j][k + 1][0], dp[i][j][k][t]);
                        }
                        // Gán bit thứ i+1 = 1
                        selfAdd(dp[i + 1][j][k + 1][t + 1], dp[i][j][k][t]);
                    }
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k + j <= n; ++k) {
                for (int t = 0; t <= k; ++t) {
                    int maxs = t < v ? max(j, k - t) : max(j, k);
                    if (maxs >= u) {
                        selfAdd(res, dp[n][j][k][t]);
                    }
                }
            }
        }
        cout << res << '\n';
    }

    return 0;
}

Subtask $4$ ($20\%$ số điểm): $n \leq 200$.

Tutorial

Từ subtask $\texttt{3}$, dễ nhận thấy rằng thay vì lưu độ dài đoạn bit thoả mãn lớn nhất, ta chỉ cần lưu trạng thái cho biết độ dài đoạn bit thoả mãn lớn nhất đã $\geq u$ hay chưa.
Từ đó $\texttt{dp}[i][j][k][t]$ được định nghĩa lại thành số lượng dãy nhị phân với:

$i$ là độ dài của dãy nhị phân,
$j$ là độ dài đoạn bit thoả mãn dài nhất ở cuối (cho phép chứa đoạn bit $1$ độ dài $< v$ ở cuối nếu có),
$k$ là số lượng bit $1$ ở cuối ($k = 0$ nếu không có),
$t$ có giá trị $0$ hoặc $1$, $t = 0$ nếu độ dài đoạn bit thoả mãn lớn nhất (không tính đoạn bit thoả mãn dài nhất ở cuối được phép chứa đoạn bit $1$ độ dài $< v$ ở cuối nếu có) chưa đạt đến $u$, $t = 1$ nếu ngược lại.

$\texttt{dp}[i][j][k][t]$ được tính như sau:

code

C++

memset(dp, 0, sizeof dp);
dp[0][0][0][0] = 1;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
        for (int k = 0; k <= j; ++k) {
            for (int t = 0; t < 2; ++t) {
                if (dp[i][j][k][t] == 0) {
                    continue;
                }
                // Gán bit thứ i+1 = 0
                if (k > 0 && k < v) {
                    dp[i+1][1][0][t||(j-k>=u)] += dp[i][j][k][t];
                } 
                else {
                    dp[i+1][j+1][0][t] += dp[i][j][k][t];
                }
                // Gán bit thứ i+1 = 1
                dp[i+1][j+1][k+1][t] += dp[i][j][k][t];
            }
        }
    }
}

Kết quả của bài toán được tính như sau:

code

C++

int res = 0;
for (int j = 0; j <= n; ++j) {
    for (int k = 0; k <= j; ++k) {
        for (int t = 0; t < 2; ++t) {
            bool ok = t || (j - k * (k < v) >= u);
            if (ok) {
                res += dp[n][j][k][t];
            }
        }
    }
}

Độ phức tạp: $\mathcal{O}(T \times n^3)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 207;
const int MOD = 1e9 + 7;

int numTest;
int n, v, u;
int dp[MAX_N][MAX_N][MAX_N][2];

inline int add(int x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
    return x;
}

inline void selfAdd(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

inline int mul(long long x, int y) {
    return x * y % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("BITSTR.inp", "r", stdin);
    freopen("BITSTR.out", "w", stdout);

    cin >> numTest;
    while (numTest--) {
        cin >> n;
        cin >> u >> v;
        if (u < v) {
            swap(u, v);
        }

        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int k = 0; k <= j; ++k) {
                    for (int t = 0; t < 2; ++t) {
                        if (dp[i][j][k][t] == 0) {
                            continue;
                        }
                        // Gán bit thứ i+1 = 0
                        if (k > 0 && k < v) {
                            selfAdd(dp[i + 1][1][0][t || (j - k >= u)], dp[i][j][k][t]);
                        } else {
                            selfAdd(dp[i + 1][j + 1][0][t], dp[i][j][k][t]);
                        }
                        // Gán bit thứ i+1 = 1
                        selfAdd(dp[i + 1][j + 1][k + 1][t], dp[i][j][k][t]);
                    }
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= j; ++k) {
                for (int t = 0; t < 2; ++t) {
                    bool ok = t || (j - k * (k < v) >= u);
                    if (ok) {
                        selfAdd(res, dp[n][j][k][t]);
                    }
                }
            }
        }
        cout << res << '\n';
    }

    return 0;
}

Subtask $5$ ($20\%$ số điểm): Không có ràng buộc gì thêm.

Tutorial

Trước hết, ta cần nhận thấy rằng cách giải các subtask ở trên phải quản lý đồng thời đoạn bit $1$ có độ dài $\geq v$ và các bit $0$, như thế sẽ tốn hai trạng thái. Vì vậy cần phải có một cách để xử lý độc lập hai phần này.
Từ đó ta có thể nghĩ ra một cách như sau:

Xây dựng các dãy nhị phân chứa các bit $0$ và các đoạn bit $1$ có độ dài $\bf{< u}$
Với mỗi đoạn bit $0$ trong dãy nhị phân xây dựng được, đếm số lượng cách biến đổi đoạn đó thành một đoạn bit thoả mãn, chú ý là nhớ giữ cho bit ở đầu và cuối đoạn = $0$ nếu có đoạn bit $1$ ở trước hoặc sau đó để ngăn cách các đoạn bit $1$ với nhau.
Dùng quy tắc nhân để tính được số lượng dãy nhị phân thoả mãn được xây dựng từ dãy nhị phân ở bước $\texttt{1}$.

Với cách làm này ta có thể tách riêng phần tính toán ra làm hai giúp thuật toán được tối ưu.

Chú ý

Trước khi đi vào phần quy hoạch động, ta cần xét trước trường hợp $u = 1$ hoặc $v = 1$. Kết quả của trường hợp này là $2^n$. Nếu gặp trường hợp này thì cách quy hoạch động sẽ không đúng. Sau khi đảm bảo $1 < v \leq u$, ta sẽ chuyển sang phần quy hoạch động.

Như vậy sẽ có hai phần tính quy hoạch động:

Gọi $\texttt{f}[i][j]$ là số lượng đoạn bit thoả mãn với $i$ là độ dài đoạn bit và $j$ là giá trị bit ở cuối đoạn.
Gọi $\texttt{dp}[i][j][k][t]$ là số lượng dãy nhị phân với:
- $i$ là độ dài dãy, $j$ là số lượng bit $0$ hoặc bit $1$ ở cuối,
- $k$ là giá trị bit ở cuối dãy,
- $t$ là kiểm tra độ dài đoạn bit $0$ dài nhất trong dãy đã đạt đến $u$ hay chưa, $t = 0$ nếu chưa, $t = 1$ nếu ngược lại.

Lưu ý

Trong quá trình xây dựng $\texttt{dp}[i][j][k][t]$, $\texttt{f}[i][j]$ sẽ được tính lồng vào.

$\texttt{f}[i][j]$ được tính như sau:

code

C++

memset(f, 0, sizeof f);
f[1][0] = 1;
for (int i = 2; i <= n; ++i) {
    f[i][0] = f[i-1][0] + f[i-1][1];
    if (v <= i) {
        f[i][1] = 1;
        for (int j = v; j < i; ++j) {
            f[i][1] += f[i-j][0];
        }
    }
}

$\texttt{dp}[i][j][k][t]$ được tính như sau:

code

C++

memset(dp, 0, sizeof dp);
dp[1][1][0][0] = dp[1][1][1][0] = 1;
for (int i = 1; i < n; ++i) {
    for (int j = 1; j <= i; ++j) {
        for (int k = 0; k < 2; ++k) {
            // Bit ở cuối = 0, gán bit thứ i+1 = 0
            dp[i+1][j+1][0][k||(j+1>=u)] += dp[i][j][0][k];
            // Bit ở cuối = 0, gán bit thứ i+1 = 1
            dp[i+1][1][1][k] += dp[i][j][0][k] * f[j-(j!=1&&i!=j)][0];
            // Bit ở cuối = 1, gán bit thứ i+1 = 0
            dp[i+1][1][0][k] += dp[i][j][1][k];
            // Bit ở cuối = 1, gán bit thứ i+1 = 1
            if (j < v-1) {
                dp[i+1][j+1][1][k] += dp[i][j][1][k];
            }
        }
    }
}

Kết quả bài toán được tính như sau:

code

C++

int res = 0;
for (int i = 1; i <= n; ++i) {
    res += dp[n][i][0][1] * (f[i-(i!=1&&i!=n)][0] + f[i-(i!=1&&i!=n)][1]);
    res += dp[n][i][1][1];
}

Độ phức tạp: $\mathcal{O}(T \times n^2)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2003;
const int MOD = 1e9 + 7;

int numTest;
int n, u, v;
int f[MAX_N][2], dp[MAX_N][MAX_N][2][2];

inline int add(int x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
    return x;
}

inline void selfAdd(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

inline int mul(long long x, int y) {
    return x * y % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("BITSTR.inp", "r", stdin);
    freopen("BITSTR.out", "w", stdout);

    cin >> numTest;
    while (numTest--) {
        memset(dp, 0, sizeof dp);
        memset(f, 0, sizeof f);
        cin >> n;
        cin >> u >> v;
        if (u < v) {
            swap(u, v);
        }

        if (v == 1) {
            int res = 1;
            for (int i = 1; i <= n; ++i) {
                res = mul(res, 2);
            }
            cout << res << '\n';
        } else {
            f[1][0] = 1;
            for (int i = 2; i <= n; ++i) {
                f[i][0] = add(f[i - 1][0], f[i - 1][1]);
                if (v <= i) {
                    f[i][1] = 1;
                    for (int j = v; j < i; ++j) {
                        selfAdd(f[i][1], f[i - j][0]);
                    }
                }
            }

            dp[1][1][0][0] = dp[1][1][1][0] = 1;
            for (int i = 1; i < n; ++i) {
                for (int j = 1; j <= i; ++j) {
                    for (int k = 0; k < 2; ++k) {
                        // Bit ở cuối = 0, gán bit thứ i+1 = 0
                        selfAdd(dp[i + 1][j + 1][0][k || (j + 1 >= u)], dp[i][j][0][k]);
                        // Bit ở cuối = 0, gán bit thứ i+1 = 1
                        dp[i + 1][1][1][k] = (dp[i + 1][1][1][k] + 1LL * dp[i][j][0][k] * f[j - (j != 1 && i != j)][0]) % MOD;
                        // Bit ở cuối = 1, gán bit thứ i+1 = 0
                        selfAdd(dp[i + 1][1][0][k], dp[i][j][1][k]);
                        // Bit ở cuối = 1, gán bit thứ i+1 = 1
                        if (j < v - 1) {
                            selfAdd(dp[i + 1][j + 1][1][k], dp[i][j][1][k]);
                        }
                    }
                }
            }

            int res = 0;
            for (int i = 1; i <= n; ++i) {
                res = (res + 1LL * dp[n][i][0][1] * (f[i - (i != 1 && i != n)][0] + f[i - (i != 1 && i != n)][1])) % MOD;
                selfAdd(res, dp[n][i][1][1]);
            }

            cout << res << '\n';
        }
    }
    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.

Hướng dẫn cho LQDOJ CUP 2022 - Round 5 - BITSTR

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).

Subtask \(2\) (\(20\%\) số điểm): \(u = n\).

Subtask \(3\) (\(20\%\) số điểm): \(n \leq 40\).

Subtask \(4\) (\(20\%\) số điểm): \(n \leq 200\).

Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận