Khi gặp bài toán liên quan đến dãy ngoặc, thay vì cố gắng tính toàn bộ đóng góp ở bước cuối, hãy chia nhỏ từng phần để xử lý. Đây là điểm mấu chốt dễ bị bỏ qua nhưng lại giúp tối ưu hóa thuật toán.

Xử lý dãy ngoặc hiệu quả

Bắt đầu bằng việc xây dựng dãy ngoặc theo cách thông thường: với mỗi dấu ngoặc đóng tại vị trí i, tìm vị trí j tương ứng của dấu ngoặc mở. Khi đó, số lượng đoạn hợp lệ có thể nối tiếp vào đoạn hiện tại được tính bằng giá trị tại j-1. Tổng kết quả chính là tổng số cặp ngoặc hợp lệ cộng với tổng các giá trị này tại mọi vị trí đóng.

Mở rộng cho trường hợp nhiều ngoặc lồng nhau: khi một vị trí chứa nhiều dấu ngoặc đóng, ta cần lặp lại quá trình ghép nối cho đến khi hết ngoặc hoặc khớp hoàn toàn với một nhóm ngoặc mở. Nếu khớp hoàn toàn, vị trí hiện tại có thể kế thừa giá trị từ vị trí trước đó. Lưu ý chỉ tính đóng góp một lần cho mỗi vị trí, dù nó có nhiều ngoặc đóng.

Dưới đây là mã nguồn minh họa:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAXN = 10000005;
ll n, x, y, z, mod0, mod1, seq[MAXN];
ll ptr = 0, total = 0, link[MAXN], res = 0;
bool used[MAXN];
pair<ll, ll> stk[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> x >> y >> z >> mod0 >> mod1 >> seq[0] >> seq[1];
    for (int i = 2; i < n; ++i) {
        ll cur_mod = (i & 1) ? mod1 : mod0;
        seq[i] = (seq[i-1] * x + seq[i-2] * y + z) % cur_mod + 1;
    }

    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            stk[++ptr] = {i, seq[i]};
        } else {
            while (seq[i] > 0 && ptr > 0) {
                auto top = stk[ptr--];
                if (top.second <= seq[i]) {
                    res += top.second;
                    if (top.second > 0 && !used[top.first - 1])
                        res += link[top.first - 1];
                    seq[i] -= top.second;
                } else {
                    res += seq[i];
                    top.second -= seq[i];
                    seq[i] = 0;
                    stk[++ptr] = top;
                }
            }
            if (seq[i] > 0) {
                ptr = 0;
                used[i] = true;
                link[i] = 0;
            } else {
                link[i]++;
            }
        }
    }

    cout << res << endl;
    return 0;
}

Tối ưu đếm dãy con XOR

Bài toán thứ hai yêu cầu đếm số dãy con có độ dài ít nhất 4 sao cho tổng XOR của mọi 4 phần tử liên tiếp bằng giá trị cho trước s. Với dữ liệu nhỏ, có thể dùng DP 4 chiều, nhưng với giới hạn lớn hơn, cần nén trạng thái.

Đầu tiên, sử dụng mảng dp[x][y][z] lưu số cách chọn dãy con kết thúc bởi ba phần tử có giá trị x, y, z. Chuyển trạng thái bằng cách duyệt phần tử tiếp theo thỏa mãn điều kiện XOR. Dùng mảng phụ để tối ưu truy vấn, giảm độ phức tạp về O(n³ + 2^m·n).

Tiếp tục tối ưu: do các phần tử phân biệt, không tồn tại 5 phần tử liên tiếp mà cả hai bộ 4 phần tử đều có XOR bằng s. Vì vậy, chỉ cần lưu hai phần tử cuối cùng trong dãy con. Công thức chuyển trạng thái trở thành:

dp[x][y] = Σ dp[y][z] - Σ dp[z][i] (với a_i ⊕ a_x ⊕ a_y ⊕ a_z = s)

Hai tổng này đều có thể duy trì bằng mảng phụ, đưa độ phức tạp về O(n(n + 2^m)).

Mã nguồn tham khảo:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAXN = 4097, MOD = 998244353;
ll n, m, target, val[MAXN], result = 0;
ll dp[MAXN][MAXN], sum_val[MAXN], acc[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> target;
    for (int i = 1; i <= n; ++i)
        cin >> val[i];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            ll need = val[i] ^ val[j] ^ target;
            sum_val[val[j]] = (acc[j] + 1 - dp[j-1][need] + MOD) % MOD;
            acc[i] = (acc[i] + sum_val[val[j]]) % MOD;
        }
        for (int j = 0; j < (1 << m); ++j)
            dp[i][j] = (dp[i-1][j] + sum_val[val[i] ^ j]) % MOD;
        result = (result + acc[i]) % MOD;
    }

    cout << (result + n) % MOD << endl;
    return 0;
}