Ta coi bài toán tìm dãy ngoặc đúng như là bài toán điền các số ~-1~ và ~1~ vào mảng ~a~ độ dài ~n~ sao cho: 1) tổng tiền tố nhỏ nhất là ~0~, và 2) tổng của cả dãy là ~0~.

Ta coi mỗi vị trí ~i~ thuộc một trong bốn loại sau:

• Loại ~1~: ~i~ là mút trái (mút ~l~) của một cặp nào đó.

• Loại ~2~: ~i~ là mút trái (mút ~r~) của một cặp nào đó.

• Loại ~3~: ~i~ nằm hoàn toàn bên trong đoạn ~(l_j, r_j)~ của một cặp nào đó.

• Loại ~4~: ~i~ không nằm bên trong bất kì đoạn nào.

Subtask 1:

Ta có thể giải subtask bằng quy hoạch động: ~dp_{i, s, t}~ lưu số lượng cách điền các vị trí tính tới ~i~ sao cho tổng tiền tố tới ~i~ là ~s~; ngoài ra, ~t~ lưu giá trị của mút ~l~ cuối cùng tính tới ~i~ (~-1~ hoặc là ~1~). Dễ dàng nhận thấy thuật toán này có độ phức tạp là ~O(n^2)~.

Trước khi đến với các subtask tiếp theo, ta định nghĩa các mảng sau:

• ~tp_i~ là loại của vị trí ~i~ (tính từ ~1~ tới ~4~).

• ~id_i~ là số lượng kí tự loại ~3~/~4~ tính tới ~i~. Nói cách khác, ~i~ là kí tự loại ~3~/~4~ thứ ~id_i~.

• ~pr_i~ là tổng tiền tố các giá trị loại ~3~/~4~ tính tới vị trí ~i~.

• ~pv_i~ là kí tự loại ~3~/~4~ ngay trước ~i~, và ~nx_i~ là kí tự loại ~3~/~4~ tiếp theo sau ~i~.

• ~cl_i~ là số lượng kí tự loại ~1~ tính tới ~i~.

• ~cr_i~ là số lượng kí tự loại ~2~ tính tới ~i~.

Subtask 2:

Ở subtask này, các vị trí loại ~3~ không tồn tại.

Ý tưởng chung của subtask này là như sau: ta sẽ điền các vị trí loại ~4~ trước, rồi đếm số cách điền các vị trí loại ~1~ và loại ~2~. Điều kiện để điền các vị trí loại ~4~ là ~pr_i \ge 0~ với mọi ~i~, và ~pr_n = 0~. Sau khi điền các vị trí loại ~4~, nhận thấy rằng với một cặp ~(l_j, r_j)~ nào đó:

• Nếu ~pr_{l_j} = 0~, chỉ có đúng một cách điền ~l_j~ và ~r_j~ (~s_{l_j} = 1~ và ~s_{r_j} = -1~).

• Còn lại, cả hai cách điền ~l_j~ và ~r_j~ đều hợp lệ.

Nhận xét này dẫn tới ý tưởng quy hoạch động sau. Gọi ~dp_i~ là số lượng cách điền các vị trí tính tới ~i~ sao cho ~pr_i = 0~, và mảng này chỉ được định nghĩa trên các vị trí ~i~ thuộc loại ~4~; ngoài ra, định nghĩa ~dp_0 = 1~. Nhận xét là đáp án chính xác là ~dp_t~ với ~t~ là vị trí loại ~4~ cuối cùng (do chỉ có đúng một cách điền các vị trí loại ~1~ và ~2~ sau ~t~). Để tính ~dp_i~, ta duyệt qua các vị trí ~j~ là vị trí loại ~4~ cuối cùng có ~pr_j = 0~. Nhận thấy là:

• Số lượng cách điền các vị trí loại ~4~ trong nửa khoảng ~(j, i]~ là ~\operatorname{Cat}\left(\frac{k - 2}{2}\right)~, với ~k = id_i - id_j~ là số lượng vị trí loại ~4~ trong nửa khoảng ~(j, i]~ (nếu ~k~ lẻ thì số này là ~0~); đây là số lượng dãy ngoặc đúng độ dài ~k~ không chạm ~0~.

• Số lượng cách điền các vị trí loại ~1~ hoặc ~2~ trong nửa khoảng ~(j, i]~ chính xác là ~2^c~, với ~c~ là số lượng cặp ~(l_j, r_j)~ nằm hoàn toàn trong đoạn ~[nx_j, i]~; (đây là vì ta biết được ~pr_x > 0~ của mọi vị trí ~x~ thuộc loại ~4~). Bởi số lượng cặp nằm hoàn toàn trong đoạn ~[nx_j, i]~ đúng bằng số lượng vị trí loại ~1~ nằm trong đoạn này, số lượng cách điền này bằng ~2^{cl_i - cl_{nx_j}}~.

Nói cách khác $$dp_i = \sum_{\substack{j < i \\ tp_j = 4}} dp_j \cdot 2^{cl_i - cl_{nx_j}} \cdot\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)$$

Cài đặt công thức quy hoạch động này cho lời giải có độ phức tạp ~O(n^2)~, nhưng ta có thể cải tiến độ phức tạp như sau. Nhận thấy nếu ta định nghĩa ~f_{id_i} = dp_i \cdot 2^{-cl_{nx_i}}~ và ~g_k = \operatorname{Cat}\left(\frac{k - 2}{2}\right)~, thì

$$dp_i = 2^{cl_i} \sum_{j=0}^{id_i - 1} f_{j} \cdot g_{id_i - j}$$

Công thức quy hoạch động này có thể dễ dàng được tối ưu bằng kĩ thuật online FFT (để rõ hơn, nếu gọi ~di~ là hàm nghịch đảo của hàm ~id~, thì công thức trên là ~dp_{di_i} = 2^{cl_{di_i}} \sum_{j=0}^{i - 1} f_{j} \cdot g_{i - j}~). Độ phức tạp của thuật toán sẽ là ~O(n \log^2 n)~.

Subtask 3:

Ý tưởng ở đây tương tự với subtask 2: ta sẽ điền trước giá trị cho các vị trí ~3~/~4~, rồi điền các vị trí ~1~/~2~ sau.

Ta cần mở rộng các quan sát ở trên. Để điền các vị trí ~3~/~4~, ta cần các điều kiện sau:

• ~pr_i \ge -1~ với mọi ~i~.

• Nếu ~pr_i = -1~, vị trí ~i~ và vị trí ~i + 1~ phải có loại ~3~.

• ~pr_n = 0~.

Sau đó, để điền các vị trí ~1~/~2~ ta có nhận xét sau với mọi cặp ~(l_j, r_j)~:

• Nếu tồn tại ~i \in [l_j, r_j]~ mà ~pr_i = 0~, chỉ có một cách điền ~l_j~ và ~r_j~.

• Còn lại, cả hai cách điền ~l_j~ và ~r_j~ đều hợp lệ.

Đến đây, phần quy hoạch động khá giống phần quy hoạch động của subtask 2. Gọi ~dp_{i, 0}~ là số lượng cách điền các vị trí tính tới ~i~ sao cho ~pr_i = 0~, và ~dp_{i, -1}~ là số lượng cách điền các vị trí tính tới ~i~ sao cho ~pr_i = -1~. ~dp_{i, -1}~ khá dễ xử lý: nếu ~i~ là một vị trí cho phép có ~pr_i = -1~ thì ~dp_{i, -1} = dp_{pv_i, 0}~. Với ~dp_{i, 0}~, ta có hai trường hợp:

• ~s_i = 1~, hay ~pr_{pv_i} = -1~. Trong trường hợp này ta cần cộng ~dp_{pv_i, -1}~ vào đáp án.

• ~s_i = -1~ hay ~pr_{pv_i} = 1~. Ở đây, ta lại một lần nữa duyệt qua các vị trí ~j~ là vị trí loại ~3~/~4~ cuối cùng có ~pr_j = 0~. Nhận thấy là:

  • Số lượng cách điền các vị trí loại ~3~/~4~ trong nửa khoảng ~(j, i]~ là ~\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)~.

  • Số lượng cách điền các vị trí loại ~1~ hoặc ~2~ trong nửa khoảng ~(j, i]~ chính xác là ~2^c~, với ~c~ là số lượng cặp ~(l_j, r_j)~ nằm hoàn toàn trong đoạn ~[nx_j, i]~. Ta có thể chứng minh được là ~c = \max(0, cr_i - cl_{nx_j})~.

Nói cách khác $$dp_{i, 0} = dp_{pv_i, -1} + \sum_{\substack{j < i \\ tp_j \in \{3, 4\}}} dp_{j, 0} \cdot 2^{\max(0, cr_i - cl_{nx_j})} \cdot\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)$$

Công thức quy hoạch động này không thể biến đổi trực tiếp về dạng có thể dùng online FFT được (bởi biểu thức ~\max~ trên lũy thừa của ~2~). Ở đây, ta có nhận xét quan trọng sau: với mọi ~j < i~, ta có ~cr_i - cl_{nx_j} \ge -1~. Bởi thế, ta có thể tách công thức trên như sau: $$dp_{i, 0} = dp_{pv_i, -1} + \left(\sum_{\substack{j < i \\ tp_j \in \{3, 4\}}} dp_{j, 0} \cdot 2^{cr_i - cl_{nx_j}} \cdot\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)\right) + \left(\sum_{\substack{j < i \\ tp_j \in \{3, 4\}\\cl_{nx_j} > cr_i}} dp_{j, 0} \cdot \frac{1}{2} \cdot\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)\right)$$

Ở đây, ~\frac{1}{2}~ xuất hiện ở tổng thứ hai vì ở tổng thứ nhất, ~dp_{j, 0} \cdot\operatorname{Cat}\left(\frac{id_i - id_j - 2}{2}\right)~ có hệ số là ~\frac{1}{2}~ nếu ~cl_{nx_j} > cr_i~, trong khi ta cần hệ số là ~1~.

Đến đây, ta lại có thể một lần nữa áp dụng kĩ thuật online FFT hai lần để tối ưu quy hoạch động với độ phức tạp là ~O(n \log^2 n)~. Cuối cùng, ta cần để ý là với ~t~ là vị trí loại ~2~/~4~ cuối cùng, đáp án của bài toán là ~dp_{t, 0}~ nếu ~t~ có loại ~2~, hoặc ~dp_{t, 0} - dp_{pv_t, -1}~ nếu ~t~ có loại ~4~ (lý do ta cần trừ ~dp_{pv_t, -1}~ trong trường hợp ~t~ có loại ~4~ là vì ta cần vị trí ~t~ có giá trị là ~-1~).

Cách cài đặt online FFT bằng nhảy bit

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

const int N = 2E5 + 5;

struct online_fft {
    const vector<mint>& g;
    vector<mint> f;
    unsigned int n;

    online_fft(const vector<mint>& g_) : g(g_), n(1), f(1) {}

    void reset() { f.clear(); f = {0}; n = 1; }

    mint get_next() { return f[n - 1]; }

    void put_last(mint s) {
        assert(f.size() >= n);
        f[n - 1] = s;
        int bit = __countr_zero(n);
        if ((1 << bit) == n) {
            f.resize(2 * n);
        }
        vector<mint> tmp = convolution(
            vector(f.begin() + n - (1 << bit), f.begin() + n),
            vector(g.begin(), g.begin() + (1 << (bit + 1)) + 1)
        );
        for (int i = 0; i < (1 << bit); i++) {
            assert(n + i < f.size());
            f[n + i] += tmp[i + (1 << bit)];
        }
        n++;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<mint> cat(N), pw(N);
    {
        vector<mint> fct(2 * N);
        fct[0] = 1;
        for (int i = 1; i < 2 * N; i++) {
            fct[i] = fct[i - 1] * i;
        }
        for (int i = 0; i < N; i++) {
            cat[i] = fct[2 * i] / fct[i + 1] / fct[i];
        }
        pw[0] = 1;
        for (int i = 1; i < N; i++) {
            pw[i] = pw[i - 1] * 2;
        }
    }

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector<int> tp(n + 2, 4), cl(n + 2), cr(n + 2), pv(n + 2), nx(n + 2);
        while (k--) {
            int l, r; cin >> l >> r;
            tp[l] = 1; tp[r] = 2;
            cl[l] = 1; cr[r] = 1;
            for (int i = l + 1; i < r; i++) {
                tp[i] = 3; // inside
            }
        }
        for (int i = 1; i <= n; i++) {
            pv[i] = tp[i - 1] >= 3 ? i - 1 : pv[i - 1];
            cl[i] += cl[i - 1];
            cr[i] += cr[i - 1];
        }
        for (int i = n; i >= 0; i--) {
            nx[i] = tp[i + 1] >= 3 ? i + 1 : nx[i + 1];
        }

        vector dp(n + 1, vector<mint>(2));
        vector<mint> f(2 * n + 1);
        for (int i = 2; i <= 2 * n; i += 2) {
            f[i] = cat[(i - 2) / 2];
        }

        mint ans = 1;
        dp[0][0] = 1;
        online_fft main_contrib(f), under_count(f);
        main_contrib.put_last(1 / pw[cl[nx[0]]]);
        under_count.put_last(1);

        for (int i = 1, max_cl = cl[nx[0]]; i <= n; i++) {
            if (tp[i] >= 3) {
                dp[i][0] = dp[pv[i]][1];
                if (tp[i] == 3 && tp[i + 1] == 3) {
                    dp[i][1] = dp[pv[i]][0];
                }
                int cur_cl = cl[nx[i]], cur_cr = cr[i];
                dp[i][0] += main_contrib.get_next() * pw[cur_cr];
                if (cur_cr < max_cl) {
                    assert(cur_cr + 1 == max_cl);
                    // these things were added with 1/2 coef, need to bump back to 1
                    dp[i][0] += under_count.get_next() / 2;
                }

                if (max_cl < cur_cl) {
                    under_count.reset();
                    max_cl = cur_cl;
                }
                main_contrib.put_last(dp[i][0] / pw[cur_cl]);
                under_count.put_last(dp[i][0]);
                // we don't want the last thing to be ( it is outside a range
                ans = dp[i][0] - (tp[i] == 3 ? 0 : dp[pv[i]][1]);
            }
        }
        cout << ans.val() << '\n';
    }
}

Cách cài đặt online FFT bằng chia để trị CDQ

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

const int N = 2E5 + 5;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<mint> cat(N), pw(N);
    {
        vector<mint> fct(2 * N);
        fct[0] = 1;
        for (int i = 1; i < 2 * N; i++) {
            fct[i] = fct[i - 1] * i;
        }
        for (int i = 0; i < N; i++) {
            cat[i] = fct[2 * i] / fct[i + 1] / fct[i];
        }
        pw[0] = 1;
        for (int i = 1; i < N; i++) {
            pw[i] = pw[i - 1] * 2;
        }
    }

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector<int> tp(n + 2, 4), cl(n + 2), cr(n + 2);
        while (k--) {
            int l, r; cin >> l >> r;
            tp[l] = 1; tp[r] = 2;
            cl[l] = 1; cr[r] = 1;
            for (int i = l + 1; i < r; i++) {
                tp[i] = 3; // inside
            }
        }
        vector<int> good = {0};
        for (int i = 1; i <= n; i++) {
            cl[i] += cl[i - 1];
            cr[i] += cr[i - 1];
            if (tp[i] >= 3) {
                good.push_back(i);
            }
        }

        int s = good.size();
        vector dp(s, vector<mint>(2));
        vector<mint> f(2 * s + 1);
        for (int i = 2; i <= 2 * s; i += 2) {
            f[i] = cat[(i - 2) / 2];
        }
        function<void(int, int)> solve = [&](int l, int r) {
            if (l + 1 == r) {
                if (l == 0) {
                    dp[l][0] = 1;
                } else {
                    dp[l][0] += dp[l - 1][1];
                    if (int i = good[l]; tp[i] == 3 && tp[i + 1] == 3) {
                        dp[l][1] += dp[l - 1][0];
                    }
                }
                return;
            }
            int m = (l + r) / 2;
            solve(l, m);

            int max_cl = cl[good[m]];
            vector<mint> a(m - l), b(m - l);
            for (int i = l; i < m; i++) {
                a[i - l] = dp[i][0] / pw[cl[good[i + 1]]];
                b[i - l] = cl[good[i + 1]] == max_cl ? dp[i][0] : 0;
            }
            vector<mint> g(f.begin(), f.begin() + r - l);
            vector<mint> ag = convolution(a, g), bg = convolution(b, g);
            for (int i = m; i < r; i++) {
                dp[i][0] += ag[i - l] * pw[cr[good[i]]] + (cr[good[i]] < max_cl ? bg[i - l] / 2 : 0);
            }

            solve(m, r);
        };

        solve(0, s);
        cout << (dp[s - 1][0] - (s == 1 || tp[good[s - 1]] == 3 ? 0 : dp[s - 2][1])).val() << '\n';
    }
}