Bài toán 1: Tối đa hóa tổng GCD của hai tập hợp

Để giải quyết bài toán chia mảng thành hai tập hợp \(B\) và \(C\) sao cho tổng ước chung lớn nhất (GCD) của chúng là lớn nhất, chúng ta cần phân tích các đặc tính của GCD.

Phân tích và Chứng minh

• Trường hợp tất cả phần tử giống nhau: Kết quả hiển nhiên là giá trị của phần tử đó nhân với 2.
• Trường hợp tồn tại ít nhất hai phần tử khác nhau: Việc gộp tất cả các phần tử có cùng giá trị vào một tập hợp duy nhất là tối ưu. Nếu chia chúng ra, GCD của tập chứa nhiều phần tử hơn sẽ không tăng, trong khi tập còn lại có thể bị giảm GCD.

Do đó, bước đầu tiên là loại bỏ các phần tử trùng lặp. Gọi \(x\) là giá trị lớn nhất trong mảng đã loại bỏ trùng lặp. Ta có thể chứng minh rằng trong cách chia tối ưu, một trong hai tập hợp sẽ chỉ chứa đúng 1 phần tử.

Chứng minh phản chứng: Giả sử cả hai tập hợp đều có từ 2 phần tử trở lên. Khi đó, GCD của mỗi tập hợp sẽ bị chặn trên bởi \(\frac{x}{2}\) (do GCD phải là ước của phần tử lớn nhất và nhỏ hơn chính nó). Tổng GCD của hai tập hợp sẽ không vượt quá \(x\). Tuy nhiên, nếu ta chọn \(B = \{x\}\), ta có \(GCD(B) = x\) và \(GCD(C) \ge 1\), tổng sẽ là \(x + 1\). Điều này mâu thuẫn với giả thuyết ban đầu, chứng tỏ tập nhỏ hơn phải có kích thước bằng 1.

Cài đặt thuật toán

Với kết luận trên, ta chỉ cần duyệt qua từng phần tử để làm tập \(B\) (kích thước 1), và tính GCD của các phần tử còn lại (tập \(C\)). Để tối ưu hóa thời gian tính toán từ \(O(N^2)\) xuống \(O(N)\), ta sử dụng mảng tiền tố (prefix) và hậu tố (suffix) để lưu trữ GCD.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

void processTestCase() {
    int size;
    cin >> size;
    vector<int> elements(size);
    for (int i = 0; i < size; ++i) cin >> elements[i];

    vector<int> prefixGcd(size), suffixGcd(size);
    prefixGcd[0] = elements[0];
    for (int i = 1; i < size; ++i) {
        prefixGcd[i] = std::gcd(prefixGcd[i - 1], elements[i]);
    }
    
    suffixGcd[size - 1] = elements[size - 1];
    for (int i = size - 2; i >= 0; --i) {
        suffixGcd[i] = std::gcd(suffixGcd[i + 1], elements[i]);
    }

    int maxSum = elements[0] + (size > 1 ? suffixGcd[1] : 0);
    maxSum = max(maxSum, (size > 1 ? prefixGcd[size - 2] : 0) + elements[size - 1]);

    for (int i = 1; i < size - 1; ++i) {
        int currentGcd = std::gcd(prefixGcd[i - 1], suffixGcd[i + 1]);
        maxSum = max(maxSum, elements[i] + currentGcd);
    }
    
    cout << maxSum << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tests;
    cin >> tests;
    while (tests--) processTestCase();
    return 0;
}

Bài toán 2: Đếm số lượng mảng con thỏa mãn điều kiện

Một mảng con được coi là "tốt" nếu nó thỏa mãn một trong các điều kiện: có độ dài 1 với phần tử duy nhất là 1, hoặc chứa đoạn con [1, 1] hoặc [1, 0, 1].

Tiếp cận giải thuật

Thay vì kiểm tra mọi mảng con (độ phức tạp \(O(N^2)\)), ta có thể duyệt ngược từ cuối mảng về đầu. Trong quá trình duyệt, ta duy trì vị trí xuất hiện gần nhất của các mẫu [1, 1] và [1, 0, 1]. Đối với mỗi vị trí bắt đầu \(i\), bất kỳ mảng con nào kết thúc tại vị trí \(j\) nằm sau các mẫu này đều là mảng con tốt. Ta cũng cần cộng thêm trường hợp mảng con chỉ có một phần tử 1.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using int64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> seq(n);
    for (int i = 0; i < n; ++i) cin >> seq[i];

    int64 validCount = 0;
    int nearest11 = n, nearest101 = n;

    for (int i = n - 1; i >= 0; --i) {
        if (i + 1 < n && seq[i] == 1 && seq[i + 1] == 1) nearest11 = i;
        if (i + 2 < n && seq[i] == 1 && seq[i + 1] == 0 && seq[i + 2] == 1) nearest101 = i;

        int limit = min({n, nearest11 + 1, nearest101 + 2});

        if (seq[i] == 1) validCount++;
        validCount += (n - limit);
    }
    cout << validCount << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Bài toán 3: Tối ưu hóa Quy hoạch động với Hàng đợi đơn điệu

Đây là bài toán kinh điển về tối ưu hóa quy hoạch động (DP) sử dụng hàng đợi đơn điệu (Monotonic Queue) để giải quyết bài toán chọn các phần tử không liên tiếp hoặc bị giới hạn bởi một cửa sổ trượt (tương tự bài toán cắt cỏ).

Thiết kế trạng thái DP

Gọi dp[i] là giá trị lớn nhất có thể đạt được khi xét đến phần tử thứ \(i\). Ta sử dụng mảng tiền tố pref để tính tổng nhanh. Công thức chuyển trạng thái có dạng:

dp[i] = max(dp[i-1], max(dp[j-1] - pref[j]) + pref[i]) với \(i - K \le j \le i\).

Để tìm giá trị max(dp[j-1] - pref[j]) trong cửa sổ trượt kích thước \(K\), ta sử dụng hàng đợi đơn điệu giảm, giúp giảm độ phức tạp từ \(O(N \cdot K)\) xuống \(O(N)\).

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;
using int64 = long long;

void solve() {
    int n, limit;
    cin >> n >> limit;
    vector<int64> vals(n);
    for (int i = 0; i < n; ++i) cin >> vals[i];

    vector<int64> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + vals[i];

    vector<int64> dp(n + 1, 0);
    deque<int> monoQ;
    monoQ.push_back(0);

    auto getValue = [&](int idx) -> int64 {
        return (idx == 0) ? 0 : dp[idx - 1] - pref[idx];
    };

    for (int right = 1; right <= n; ++right) {
        if (!monoQ.empty() && monoQ.front() < right - limit) {
            monoQ.pop_front();
        }
        
        dp[right] = max(dp[right - 1], getValue(monoQ.front()) + pref[right]);

        while (!monoQ.empty() && getValue(monoQ.back()) <= getValue(right)) {
            monoQ.pop_back();
        }
        monoQ.push_back(right);
    }
    cout << dp[n] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Bài toán 4: Tính kỳ vọng của hàm mục tiêu trên các mảng hình núi

Bài toán yêu cầu tính kỳ vọng của hàm \(F(A, K) = \sum A_i^K\) trên tất cả các mảng hình núi có độ dài \(N\) và tổng các phần tử bằng \(M\). Kỳ vọng được tính bằng tổng \(F(A, K)\) của tất cả các mảng chia cho tổng số lượng mảng hình núi.

Đếm số lượng mảng hình núi

Ta xây dựng bảng quy hoạch động ways[len][sum]. Một mảng hình núi có thể được tạo ra bằng cách:

• Cộng 1 vào tất cả các phần tử của mảng hình núi có độ dài len và tổng sum - len.
• Thêm số 0 vào bên trái hoặc bên phải của mảng hình núi có độ dài len - 1.

Để tránh đếm trùng lặp khi thêm hai số 0 ở cả hai phía, ta áp dụng nguyên lý bù trừ. Công thức chuyển trạng thái là:

ways[len][sum] = ways[len][sum-len] + 2 * ways[len-1][sum] - ways[len-2][sum]

Tính tổng F(A, K) và áp dụng Nhị thức Newton

Khi \(K=0\), tổng đơn giản là số lượng mảng nhân với \(N\). Khi \(K > 0\), ta cần tính tổng \(\sum (A_i + 1)^K\). Sử dụng khai triển Nhị thức Newton:

(A_i + 1)^K = \sum \binom{K}{j} A_i^j

Điều này cho phép ta chuyển trạng thái DP cho tổng \(F(A, K)\) dựa trên các giá trị \(F(A, j)\) với \(j \le K\). Cuối cùng, sử dụng nghịch đảo mô-đun (Modular Inverse) để tính kỳ vọng trong trường số nguyên tố.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using int64 = long long;

const int MOD = 998244353;

struct ModInt {
    int64 val;
    ModInt(int64 v = 0) : val((v % MOD + MOD) % MOD) {}
    ModInt operator-() const { return ModInt(-val); }
    ModInt& operator+=(const ModInt& o) { if ((val += o.val) >= MOD) val -= MOD; return *this; }
    ModInt& operator-=(const ModInt& o) { if ((val += MOD - o.val) >= MOD) val -= MOD; return *this; }
    ModInt& operator*=(const ModInt& o) { val = (val * o.val) % MOD; return *this; }
    ModInt operator+(const ModInt& o) const { return ModInt(*this) += o; }
    ModInt operator-(const ModInt& o) const { return ModInt(*this) -= o; }
    ModInt operator*(const ModInt& o) const { return ModInt(*this) *= o; }
    
    ModInt power(int64 exp) const {
        if (exp == 0) return 1;
        ModInt res = power(exp / 2);
        res *= res;
        if (exp % 2) res *= *this;
        return res;
    }
    
    ModInt inverse() const { return power(MOD - 2); }
    ModInt& operator/=(const ModInt& o) { return *this *= o.inverse(); }
    ModInt operator/(const ModInt& o) const { return ModInt(*this) /= o; }
};

const int MAX_M = 1005, MAX_K = 15;
ModInt powerTable[MAX_M][MAX_M];
ModInt nCr[MAX_K][MAX_K];
ModInt totalWays[MAX_M][MAX_M];
ModInt expectedSum[MAX_M][MAX_M][MAX_K];

void precompute() {
    powerTable[0][0] = 1;
    for (int j = 0; j < MAX_M; ++j) {
        for (int i = 1; i < MAX_M; ++i) {
            powerTable[i][j] = (j == 0) ? 1 : powerTable[i][j - 1] * i;
        }
    }

    nCr[0][0] = 1;
    for (int i = 0; i < MAX_K - 1; ++i) {
        for (int j = 0; j <= i; ++j) {
            nCr[i + 1][j] += nCr[i][j];
            nCr[i + 1][j + 1] += nCr[i][j];
        }
    }

    totalWays[0][0] = 1;
    for (int r = 0; r < MAX_M; ++r) {
        for (int i = 0; i < MAX_K; ++i) expectedSum[1][r][i] = powerTable[r][i];
        totalWays[1][r] = 1;
    }

    for (int len = 2; len < MAX_M; ++len) {
        for (int sum = 0; sum < MAX_M; ++sum) {
            totalWays[len][sum] = totalWays[len - 1][sum] * 2 - totalWays[len - 2][sum];
            if (sum >= len) totalWays[len][sum] += totalWays[len][sum - len];
            expectedSum[len][sum][0] = totalWays[len][sum] * len;

            for (int k = 1; k < MAX_K; ++k) {
                expectedSum[len][sum][k] = expectedSum[len - 1][sum][k] * 2 - expectedSum[len - 2][sum][k];
                if (sum >= len) {
                    for (int j = 0; j <= k; ++j) {
                        expectedSum[len][sum][k] += nCr[k][j] * expectedSum[len][sum - len][j];
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    
    int tests;
    cin >> tests;
    while (tests--) {
        int n, m, k;
        cin >> n >> m >> k;
        ModInt ans = expectedSum[n][m][k] / totalWays[n][m];
        cout << ans.val << "\n";
    }
    return 0;
}