Meet in the Middle

Chia đôi dãy rồi ghép hai nửa

Bài toán: cho $a_1, \dots, a_n$ và $x$, đếm số tập con có tổng bằng $x$. Hai phần tử cùng giá trị ở hai vị trí khác nhau cho hai tập con khác nhau. Duyệt thẳng là $2^n$ tập con: $n = 20$ mất vài mili giây, $n = 30$ sát một giây, $n = 40$ hết hy vọng. Quy hoạch động theo tổng (bài 12) tốn $O(nx)$, rất tốt khi $x$ cỡ $10^6$ nhưng vô nghĩa khi $x$ tới $10^9$.

Cắt dãy ở giữa. Đặt $h = \lfloor n/2 \rfloor$: nửa trái gồm $a_1, \dots, a_h$, nửa phải gồm $a_{h+1}, \dots, a_n$. Mỗi tập con $T$ của cả dãy tách được thành đúng một cặp $(T_L, T_R)$, phần của $T$ nằm ở nửa trái và phần nằm ở nửa phải; ngược lại mỗi cặp ghép lại thành đúng một $T$, và $\mathrm{sum}(T) = \mathrm{sum}(T_L) + \mathrm{sum}(T_R)$. Gọi $L$ là danh sách tổng của mọi tập con nửa trái (đủ $2^h$ phần tử, kể cả 0 của tập rỗng, tổng trùng thì xuất hiện nhiều lần), $R$ tương tự cho nửa phải. Khi đó số tập con có tổng bằng $x$ đúng bằng số cặp $(u, v)$ với $u$ lấy trong $L$, $v$ lấy trong $R$ và $u + v = x$, trong đó $(u, v)$ là cặp vị trí trong hai danh sách. Thử mọi cặp vẫn là $2^n$, nhưng bài đã đổi bản chất: không còn lục trong không gian tập con, mà chỉ tìm cặp có tổng $x$ giữa hai danh sách số, việc làm được bằng sắp xếp.

Ví dụ với dãy $(2, 3, 5, 1, 4, 6)$ và $x = 12$, ta có $h = 3$. Nửa trái $(2, 3, 5)$ cho $L = (0, 2, 3, 5, 5, 7, 8, 10)$, số 5 xuất hiện hai lần, từ $\{5\}$ và từ $\{2, 3\}$. Nửa phải $(1, 4, 6)$ cho $R = (0, 1, 4, 5, 6, 7, 10, 11)$. Các cặp có tổng 12 là $2 + 10$, hai lần $5 + 7$, $7 + 5$ và $8 + 4$: năm cặp, nên có 5 tập con.

Sinh tổng của một nửa. Bắt đầu với $S = (0)$. Thêm phần tử $a$: mỗi tập con cũ hoặc không lấy $a$ (giữ tổng $s$), hoặc lấy $a$ (tổng $s + a$), nên danh sách mới là $S$ nối với $S + a$, gấp đôi. Số phép cộng của cả nửa là $1 + 2 + \dots + 2^{k-1} < 2^k$. Muốn danh sách đã sắp mà không tốn sort: nếu $S$ đã sắp thì $S + a$ cũng đã sắp, vì cộng cùng một hằng số không đổi thứ tự (kể cả khi $a$ âm), và hai danh sách đã sắp trộn thành một trong thời gian tuyến tính bằng merge. Cả nửa tốn $O(2^k)$, không có thừa số $\log$.

Khi mọi $a_i$ dương và chỉ cần các tổng không vượt $x$, có thể bỏ ngay các tổng vượt $x$ lúc sinh. Mẹo này chỉ đúng với số không âm.

Ghép bằng hai con trỏ. Đặt $i$ ở đầu $L$ (nhỏ nhất), $j$ ở cuối $R$ (lớn nhất), xét $s = L_i + R_j$. Nếu $s < x$ thì $L_i$ không ghép được với phần tử còn lại nào của $R$, vì mọi $R_{j'}$ với $j' \le j$ đều không lớn hơn $R_j$; bỏ $L_i$. Nếu $s > x$ thì tương tự bỏ $R_j$. Mỗi bước dịch một con trỏ, nên sau tối đa $|L| + |R|$ bước mọi cặp đã được xét. Khi $s = x$ phải cẩn thận với giá trị lặp: gọi $c_L$ là số phần tử liên tiếp bằng $L_i$ và $c_R$ là số phần tử liên tiếp bằng $R_j$; mọi cặp giữa hai nhóm đều có tổng $x$, nên cộng $c_L \cdot c_R$ rồi nhảy qua cả hai nhóm. Chỉ dịch mỗi con trỏ một bước thì ví dụ trên ra 4 thay vì 5.

Cắt ở đâu. Cắt ở vị trí $k$ thì chi phí cỡ $2^k + 2^{n-k} \ge 2 \cdot 2^{n/2}$, dấu bằng khi $k = n/2$. Cắt lệch làm mất hết lợi ích: tách 10 và 30 phần tử cho nửa phải $2^{30} \approx 10^9$ tổng, chỉ riêng việc lưu đã cỡ 8 GB. Vài con số để ước lượng, với long long 8 byte: $n = 30$ mỗi nửa $32768$ tổng, nhẹ như không; $n = 40$ mỗi nửa $2^{20} \approx 10^6$ tổng, 8 MB một danh sách; $n = 50$ mỗi nửa $3{,}4 \cdot 10^7$ tổng, 256 MB, bộ nhớ chặn đường trước thời gian. Vì vậy kỹ thuật dùng cho $n$ tới khoảng 40 đến 45. Nếu mỗi phần tử có $c$ lựa chọn thay vì hai, mỗi nửa có $c^{n/2}$ trạng thái: với $c = 3$, $n$ chỉ tới cỡ 24 đến 26.

Ví dụĐếm Tổng Mục Tiêu

Đề. Cho $n \le 40$ số nguyên dương $a_i \le 10^9$ và $x \le 10^9$. Đếm số tập con (theo vị trí) có tổng đúng $x$.

Lời giải. Đúng khung ở trên: chia dãy làm hai nửa, sinh danh sách đã sắp các tổng tập con của từng nửa, rồi đếm các cặp $(u, v)$ với $u + v = x$. Mỗi tập con của cả dãy tách duy nhất thành phần thuộc nửa trái và phần thuộc nửa phải, nên mỗi tập con có tổng $x$ ứng với đúng một cặp vị trí $(u, v)$ trong hai danh sách. Tổng một nửa lên tới $2 \cdot 10^{10}$ và đáp án tới $2^{40}$, nên mọi biến là ll.

Bước 1: sinh tổng tập con đã sắp. Bắt đầu với danh sách $\{0\}$ (tập rỗng). Thêm phần tử $a_i$ thì mỗi tập con cũ cho hai tập con mới: không lấy $a_i$ (tổng giữ nguyên) và lấy $a_i$ (tổng cộng $a_i$). Danh sách cũ s đã sắp, nên t = s + a[i] cũng đã sắp, và merge trộn hai danh sách đã sắp thành một danh sách đã sắp trong thời gian tuyến tính. Sau $k$ phần tử, danh sách có $2^k$ số.

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        vector<ll> t(s.size()), c(2 * s.size());
        for (ll k = 0; k < (ll)s.size(); k++) t[k] = s[k] + a[i];
        merge(s.begin(), s.end(), t.begin(), t.end(), c.begin());
        s = c;
    }
    return s;
}

Bước 2: ghép bằng hai con trỏ. $i$ đi từ đầu $L$ lên, $j$ đi từ cuối $R$ xuống. Tổng nhỏ hơn $x$ thì phải tăng $L_i$; lớn hơn thì phải giảm $R_j$. Gặp tổng bằng $x$, hai danh sách có thể có nhiều giá trị bằng nhau liền nhau: đếm khối $L_i = u$ (dài cu) và khối $R_j = v$ (dài cv), mọi cặp giữa hai khối đều hợp lệ nên cộng cu * cv, rồi bước qua cả hai khối.

ll i = 0, j = R.size() - 1, ans = 0;
while (i < (ll)L.size() && j >= 0) {
    if (L[i] + R[j] < x) i++;
    else if (L[i] + R[j] > x) j--;
    else {
        ll u = L[i], v = R[j], cu = 0, cv = 0;
        while (i < (ll)L.size() && L[i] == u) i++, cu++;
        while (j >= 0 && R[j] == v) j--, cv++;
        ans += cu * cv;
    }
}

Với test ví dụ $(1, 2, 3, 3)$ và $x = 6$: $L = (0, 1, 2, 3)$, $R = (0, 3, 3, 6)$; các cặp là $0 + 6$ một lần và $3 + 3$ hai lần, tổng 3.

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

ll n, x, a[45];
vector<ll> L, R;

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        vector<ll> t(s.size()), c(2 * s.size());
        for (ll k = 0; k < (ll)s.size(); k++) t[k] = s[k] + a[i];
        merge(s.begin(), s.end(), t.begin(), t.end(), c.begin());
        s = c;
    }
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> x;
    for (ll i = 0; i < n; i++) cin >> a[i];
    L = gen(0, n / 2);
    R = gen(n / 2, n);
    ll i = 0, j = R.size() - 1, ans = 0;
    while (i < (ll)L.size() && j >= 0) {
        if (L[i] + R[j] < x) i++;
        else if (L[i] + R[j] > x) j--;
        else {
            ll u = L[i], v = R[j], cu = 0, cv = 0;
            while (i < (ll)L.size() && L[i] == u) i++, cu++;
            while (j >= 0 && R[j] == v) j--, cv++;
            ans += cu * cv;
        }
    }
    cout << ans << '\n';
}

Input4 6
1 2 3 3

Output3

Mỗi nửa sinh trong $O(2^{n/2})$ nhờ trộn thay vì sắp, ghép cũng $O(2^{n/2})$; bộ nhớ hai danh sách $2^{20}$ số.

Những câu hỏi ghép khác

Cùng khung hai con trỏ trả lời được nhiều câu hỏi khác về cặp $(u, v)$; đề thi thường chỉ đổi câu hỏi chứ không đổi khung.

• Tổng lớn nhất không vượt $T$. Với $u$ tăng dần, ngưỡng $T - u$ giảm, nên con trỏ $j$ trên $R$ chỉ lùi: lùi tới khi $u + R_j \le T$ rồi cập nhật đáp án.
• Đếm cặp có tổng không vượt $T$. Cùng con trỏ đó, mỗi $u$ cộng thêm $j + 1$, số phần tử $v \le T - u$. Số tập con có tổng trong $[A, B]$ là số cặp tổng $\le B$ trừ số cặp tổng $\le A - 1$.
• Tổng gần mục tiêu $g$ nhất. Phần tử của $R$ gần $g - u$ nhất nằm cạnh vị trí chèn của $g - u$: phần tử đầu tiên không nhỏ hơn $g - u$, hoặc phần tử ngay trước nó. Thử cả hai ứng viên rồi lấy tốt nhất.

Ta cũng có thể bỏ $R$ vào bảng băm và tra $x - u$ trong thời gian kỳ vọng $O(1)$. Cách này chỉ trả lời được câu hỏi “bằng”, không trả lời được “không vượt” hay “gần nhất”, nên với tổng số ta nghiêng về sắp xếp cộng hai con trỏ. Bảng băm chỉ cần khi tóm tắt của một nửa không có thứ tự tự nhiên, như ở phần đường đi bên dưới.

Ví dụNgân Sách Tối Ưu

Đề. Có $n \le 40$ công việc, việc $i$ tốn $a_i \le 10^9$ thời gian. Chọn một tập việc bất kỳ, kể cả rỗng, có tổng thời gian không vượt $T \le 10^9$; in tổng lớn nhất đạt được.

Lời giải. Câu hỏi “tổng lớn nhất không vượt $T$” trên cặp $(u, v)$, $u \in L$, $v \in R$. Với $u$ tăng dần, ngưỡng $T - u$ giảm, nên phần tử lớn nhất của $R$ còn dùng được chỉ lùi dần: một con trỏ $j$ đi từ cuối $R$ là đủ.

Bước 1: sinh và bỏ sớm tổng vượt $T$. Như ví dụ trước, nhưng mọi $a_i$ dương nên tổng nào đã vượt $T$ thì thêm phần tử chỉ làm nó lớn hơn; bỏ ngay. Danh sách s đã sắp nên các tổng s[k] + a[i] còn $\le T$ là một đoạn đầu: vòng for dừng ở tổng đầu tiên vượt $T$. Trộn đoạn đó với s.

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        vector<ll> t;
        for (ll k = 0; k < (ll)s.size() && s[k] + a[i] <= T; k++) t.push_back(s[k] + a[i]);
        vector<ll> c(s.size() + t.size());
        merge(s.begin(), s.end(), t.begin(), t.end(), c.begin());
        s = c;
    }
    return s;
}

Bước 2: ghép. Với mỗi $u$ của $L$ theo thứ tự tăng, lùi $j$ tới khi $u + R_j \le T$ rồi cập nhật đáp án. Vòng lùi không bao giờ đưa $j$ xuống âm, vì $R_0 = 0$ và mọi $u$ đã $\le T$ sau bước 1.

ll j = R.size() - 1, ans = 0;
for (ll u : L) {
    while (u + R[j] > T) j--;
    ans = max(ans, u + R[j]);
}

Với test ví dụ, nửa trái $(3, 5)$ cho $L = (0, 3, 5, 8)$, nửa phải $(8, 9, 12)$ cho $R = (0, 8, 9, 12)$ sau khi bỏ các tổng vượt 14; cặp $5 + 9 = 14$ là tốt nhất.

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

ll n, T, a[45];
vector<ll> L, R;

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        vector<ll> t;
        for (ll k = 0; k < (ll)s.size() && s[k] + a[i] <= T; k++) t.push_back(s[k] + a[i]);
        vector<ll> c(s.size() + t.size());
        merge(s.begin(), s.end(), t.begin(), t.end(), c.begin());
        s = c;
    }
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> T;
    for (ll i = 0; i < n; i++) cin >> a[i];
    L = gen(0, n / 2);
    R = gen(n / 2, n);
    ll j = R.size() - 1, ans = 0;
    for (ll u : L) {
        while (u + R[j] > T) j--;
        ans = max(ans, u + R[j]);
    }
    cout << ans << '\n';
}

Input5 14
3 5 8 9 12

Output14

$j$ chỉ lùi nên cả vòng ghép là $O(|L| + |R|)$; tổng cộng $O(2^{n/2})$.

Tóm tắt của một nửa không chỉ là một con số

Mỗi nửa thực chất cho ra một danh sách các tóm tắt. Một tóm tắt hợp lệ khi hai tóm tắt (một của nửa trái, một của nửa phải) đủ để làm hai việc: quyết định hai nửa có ghép được không, và tính giá trị của phương án ghép. Với bài đếm tổng, tóm tắt là một số. Nhiều bài cần nhiều hơn.

• Đúng $K$ phần tử. Tóm tắt là (tổng, số phần tử). Nửa trái dùng $c$ phần tử thì nửa phải bắt buộc dùng $K - c$, nên chia mỗi danh sách thành các nhóm theo số phần tử và chỉ ghép nhóm $c$ với nhóm $K - c$.
• Phần dư. Muốn tổng theo modulo $m$ lớn nhất, tóm tắt là phần dư của nửa; điều cần xét thêm là phép cộng có thể “cuộn vòng” qua $m$.
• Ba lô trọng lượng lớn. Tóm tắt là (trọng lượng $w$, giá trị $p$), ghép được khi $w_L + w_R \le M$. Sắp nửa phải theo trọng lượng rồi thay giá trị bằng max tiền tố (bài 02), mỗi trạng thái trái hỏi bằng một lần chặt nhị phân.
• Hai túi cân bằng. Mỗi vật có ba lựa chọn (túi 1, túi 2, bỏ lại), tóm tắt là (hiệu hai túi, tổng đã dùng), hai nửa ghép được khi hai hiệu đối nhau. Với cùng một hiệu chỉ cần giữ tổng đã dùng lớn nhất.

Điều kiện “đủ” thường bị bỏ sót ở những ràng buộc đi xuyên qua chỗ cắt. Ví dụ đếm tập con có tổng $x$ mà không chọn hai phần tử liền kề: hai tập con hợp lệ ở hai nửa vẫn có thể ghép thành tập chứa cả $a_h$ và $a_{h+1}$, hai phần tử sát chỗ cắt. Muốn đúng, tóm tắt phải ghi thêm “có chọn phần tử sát chỗ cắt hay không”, rồi ghép chỉ khi không đồng thời chọn cả hai.

Ví dụPhần Dư Tập Con Lớn Nhất

Đề. Cho $n \le 35$ số nguyên dương $a_i \le 10^9$ và $m \le 10^9$. Chọn một tập con bất kỳ, kể cả rỗng, để tổng chia $m$ dư lớn nhất; in phần dư đó.

Lời giải. Quy hoạch động theo phần dư tốn $O(nm)$, duyệt tập con tốn $2^{35}$: cả hai quá chậm. Thay $a_i$ bằng $a_i \bmod m$, sinh phần dư tổng của mỗi nửa, ta được hai danh sách $L$, $R$ gồm các số trong $[0, m)$, mỗi danh sách tối đa $2^{18}$ phần tử. Một tập con cho phần dư $(x + y) \bmod m$ với $x \in L$, $y \in R$, và có hai trường hợp:

• $x + y < m$: phần dư là $x + y$.
• $x + y \ge m$: phần dư là $x + y - m < x$, vì $y < m$. Mà $x$ đạt được khi để nửa phải rỗng, nên cặp này không bao giờ tốt hơn.

Vậy đáp án là $\max\{x + y \le m - 1\}$, đúng câu hỏi “lớn nhất không vượt ngưỡng” với ngưỡng $m - 1$.

Bước 1: sinh phần dư rồi sắp. Mỗi phần tử nhân đôi danh sách: giữ các phần dư cũ và thêm (s[k] + a[i]) % m. Ở đây phải sort chứ không trộn được như hai ví dụ trước: sau phép lấy dư, các giá trị lớn cuộn về đầu, nên danh sách mới không còn đã sắp.

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        ll sz = s.size();
        for (ll k = 0; k < sz; k++) s.push_back((s[k] + a[i]) % m);
    }
    sort(s.begin(), s.end());
    return s;
}

Bước 2: ghép với ngưỡng $m - 1$. Duyệt $x$ tăng dần, con trỏ $j$ trên $R$ chỉ lùi tới khi $x + R_j < m$. Nó dừng trước khi âm vì $R_0 = 0$ và $x < m$.

ll j = R.size() - 1, ans = 0;
for (ll x : L) {
    while (x + R[j] >= m) j--;
    ans = max(ans, x + R[j]);
}

Với test ví dụ, $L = (0, 3, 6, 7)$ từ $(6, 7)$, $R = (0, 2, 4, 6)$ từ $(4, 2)$; cặp tốt nhất là $3 + 6 = 9$.

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

ll n, m, a[40];
vector<ll> L, R;

vector<ll> gen(ll lo, ll hi) {
    vector<ll> s = {0};
    for (ll i = lo; i < hi; i++) {
        ll sz = s.size();
        for (ll k = 0; k < sz; k++) s.push_back((s[k] + a[i]) % m);
    }
    sort(s.begin(), s.end());
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        a[i] %= m;
    }
    L = gen(0, n / 2);
    R = gen(n / 2, n);
    ll j = R.size() - 1, ans = 0;
    for (ll x : L) {
        while (x + R[j] >= m) j--;
        ans = max(ans, x + R[j]);
    }
    cout << ans << '\n';
}

Input4 10
6 7 4 2

Output9

Sinh mỗi nửa $O(2^{n/2})$, sắp $O(2^{n/2} \cdot n)$, ghép tuyến tính.

Ví dụChọn Đúng K Món

Đề. Có $N \le 40$ món, món $i$ giá $a_i \le 10^{16}$. Đếm số cách chọn đúng $K$ món có tổng giá không vượt $P \le 10^{18}$.

Lời giải. Hai điều kiện, đúng $K$ món và tổng $\le P$, nên tóm tắt của mỗi tập con một nửa là cặp (tổng, số món). Mỗi cách chọn hợp lệ tách duy nhất thành $(T_L, T_R)$ với $|T_L| + |T_R| = K$, nên ta xếp các tổng của mỗi nửa vào nhóm theo số món, và chỉ ghép nhóm $c$ của nửa trái với nhóm $K - c$ của nửa phải. Mỗi cách được đếm đúng một lần ở cặp nhóm $(|T_L|, K - |T_L|)$.

Bước 1: sinh tổng kèm số món, chia theo số món. Sinh như ví dụ đầu, nhân đôi danh sách sau mỗi món, nhưng mỗi phần tử giờ là cặp (tổng, số món): lấy thêm món $a_i$ thì tổng cộng $a_i$ và số món cộng 1. Xong thì bỏ từng tổng vào nhóm theo số món của nó, rồi sắp từng nhóm.

void gen(ll lo, ll hi, vector<ll> b[]) {
    vector<pair<ll, ll>> s = {{0, 0}};
    for (ll i = lo; i < hi; i++) {
        ll m = s.size();
        for (ll k = 0; k < m; k++) s.push_back({s[k].first + a[i], s[k].second + 1});
    }
    for (auto [sum, c] : s) b[c].push_back(sum);
    for (ll c = 0; c <= hi - lo; c++) sort(b[c].begin(), b[c].end());
}

Bước 2: ghép từng cặp nhóm. Với mỗi $c$ và $d = K - c$ hợp lệ, quét $x$ tăng dần trên $L_c$, giữ $j$ là số phần tử của $R_d$ không vượt $P - x$. $P - x$ giảm nên $j$ chỉ giảm, và mỗi $x$ cộng thêm $j$ cách. $P - x$ có thể âm, khi đó $j$ về 0.

for (ll c = 0; c <= h; c++) {
    ll d = K - c;
    if (d < 0 || d > n - h) continue;
    ll j = R[d].size();
    for (ll x : L[c]) {
        while (j > 0 && R[d][j - 1] > P - x) j--;
        ans += j;
    }
}

Tổng giá tối đa $40 \cdot 10^{16} = 4 \cdot 10^{17}$, còn dưới giới hạn ll. Với test ví dụ, $K = 3$: nhóm $L_1 = (2, 3)$ ghép $R_2 = (9, 12, 13)$ được hai cách, $L_2 = (5)$ ghép $R_1 = (4, 5, 8)$ được hai cách, tổng 4.

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

ll n, K, P, a[45];
vector<ll> L[25], R[25];

void gen(ll lo, ll hi, vector<ll> b[]) {
    vector<pair<ll, ll>> s = {{0, 0}};
    for (ll i = lo; i < hi; i++) {
        ll m = s.size();
        for (ll k = 0; k < m; k++) s.push_back({s[k].first + a[i], s[k].second + 1});
    }
    for (auto [sum, c] : s) b[c].push_back(sum);
    for (ll c = 0; c <= hi - lo; c++) sort(b[c].begin(), b[c].end());
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> K >> P;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll h = n / 2;
    gen(0, h, L);
    gen(h, n, R);
    ll ans = 0;
    for (ll c = 0; c <= h; c++) {
        ll d = K - c;
        if (d < 0 || d > n - h) continue;
        ll j = R[d].size();
        for (ll x : L[c]) {
            while (j > 0 && R[d][j - 1] > P - x) j--;
            ans += j;
        }
    }
    cout << ans << '\n';
}

Input5 3 12
2 3 4 5 8

Output4

Sinh $O(2^{n/2})$, sắp $O(2^{n/2} \cdot n)$, ghép tuyến tính theo tổng kích thước các nhóm.

Gặp nhau ở giữa một phương trình

Kỹ thuật không đòi hỏi phải có tập con. Xét bài: cho dãy $a$ gồm $n$ số, đếm các bộ $(i, j, k, l)$ bất kỳ sao cho $a_i + a_j = a_k + a_l$, với $n$ cỡ 2000. Duyệt bốn chỉ số tốn $n^4 \approx 1{,}6 \cdot 10^{13}$. Nhưng phương trình đã tách sẵn hai vế: vế trái chỉ phụ thuộc cặp $(i, j)$, vế phải chỉ phụ thuộc cặp $(k, l)$. Gọi $c_s$ là số cặp có thứ tự với tổng $s$; mỗi cặp bên trái ghép với mỗi cặp bên phải cùng tổng, nên đáp án là tổng các $c_s^2$ qua mọi giá trị $s$. Với $a = (1, 2, 3)$ các tổng là $2, 3, 3, 4, 4, 4, 5, 5, 6$, các nhóm có kích thước $1, 2, 3, 2, 1$ và đáp án là $1 + 4 + 9 + 4 + 1 = 19$.

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

ll n, a[2005];
vector<ll> s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) s.push_back(a[i] + a[j]);
    sort(s.begin(), s.end());
    ll ans = 0;
    for (ll l = 0, r = 0; l < (ll)s.size(); l = r) {
        while (r < (ll)s.size() && s[r] == s[l]) r++;
        ans += (r - l) * (r - l);
    }
    cout << ans << '\n';
}

Input3
1 2 3

Output19

Thời gian $O(n^2 \log n)$ cho việc sắp xếp, so với $O(n^4)$ ban đầu. Bộ nhớ là cái giá: $n^2$ giá trị, với $n = 4000$ là $1{,}6 \cdot 10^7$ số, tức 64 MB nếu vừa int và 128 MB nếu phải long long. Khi hai vế là hai danh sách khác nhau (chẳng hạn $A_i + B_j = -(C_k + D_l)$), sắp cả hai và dùng khung hai con trỏ ở mục đầu, nhân kích thước nhóm hai bên.

Mẹo là chuyển biến sang vế bên kia cho đến khi mỗi vế chỉ chứa một nhóm biến:

• $a + b + c = d$ viết lại thành $a + b = d - c$: vế trái $n^2$ giá trị, rồi duyệt $d$ và $c$.
• $a_i + b_j + c_k + d_l = 0$ thành $a_i + b_j = -(c_k + d_l)$: hai vế mỗi vế $n^2$ giá trị.
• $ab + c = d(e + f)$ với $d \ne 0$: mỗi vế là một bộ ba, $n^3$ giá trị mỗi vế, chấp nhận được khi $n \le 100$.

Ví dụGiá Trị Lớn Nhất Từ Ba Số

Đề. Cho tập $U$ gồm $n \le 1000$ số nguyên dương đôi một khác nhau, mỗi số $\le 2 \cdot 10^8$. Tìm phần tử lớn nhất $d \in U$ sao cho có $a, b, c \in U$ (được trùng nhau) với $a + b + c = d$; đề bảo đảm có đáp án.

Lời giải. Bốn biến, duyệt thẳng $n^4$. Viết lại $a + b = d - c$: vế trái là một cặp, chỉ cần lưu mọi tổng $u_i + u_j$ với $i \le j$ (cặp không thứ tự là đủ vì chỉ hỏi có hay không), khoảng $5 \cdot 10^5$ số, rồi sắp. Vế phải là cặp $(d, c)$: thử $d$ từ lớn xuống nhỏ, với mỗi $d$ thử mọi $c$ và tra $d - c$ trong danh sách bằng chặt nhị phân; gặp lần đầu là in $d$ và dừng, vì $d$ đang thử là lớn nhất còn lại. Tổng cộng $O(n^2 \log n)$. Với test ví dụ, $d = 13$ và $c = 7$ cho $13 - 7 = 6 = 2 + 4$.

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

ll n, u[1005];
vector<ll> s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> u[i];
    sort(u, u + n);
    for (ll i = 0; i < n; i++)
        for (ll j = i; j < n; j++) s.push_back(u[i] + u[j]);
    sort(s.begin(), s.end());
    for (ll d = n - 1; d >= 0; d--) {
        for (ll c = 0; c < n; c++) {
            if (binary_search(s.begin(), s.end(), u[d] - u[c])) {
                cout << u[d] << '\n';
                return 0;
            }
        }
    }
}

Input5
1
2
4
7
13

Output13

Gặp nhau trên đường đi

Cùng ý tưởng dùng được khi lời giải là một chuỗi bước. Cho bảng $n \times m$ chứa số nguyên không âm, ta đi từ góc trên trái xuống góc dưới phải, mỗi bước sang phải hoặc xuống dưới, và muốn đếm đường đi có XOR các số trên đường bằng $K$, với $n, m \le 20$.

Mỗi đường đi có đúng $D = n + m - 2$ bước, nên số đường đi là $\binom{D}{n-1}$ (chọn $n - 1$ bước đi xuống trong $D$ bước), với bảng $20 \times 20$ là $\binom{38}{19} \approx 3{,}5 \cdot 10^{10}$: quá nhiều để duyệt. Mỗi bước làm tổng chỉ số hàng cộng cột tăng đúng 1, nên mọi đường đi sau đúng $h = \lfloor D/2 \rfloor$ bước đều rơi vào một ô trên đường chéo $i + j = h$ (đánh số từ 0), và cắt đường chéo đó đúng một lần. Ta chia đường đi tại ô này: nửa đầu đi từ góc trên trái tới đường chéo, nửa sau đi ngược từ góc dưới phải lên đường chéo. Mỗi nửa có không quá $2^{19} \approx 5 \cdot 10^5$ hướng đi.

Tóm tắt một nửa đường là (ô gặp nhau, XOR các số đã đi qua). Hai nửa chỉ ghép được khi cùng ô gặp nhau, nên ta gom các nửa đường theo ô: mỗi ô trên đường chéo có một bảng đếm từ giá trị XOR sang số nửa đường. Đây là chỗ cần bảng băm hoặc map, vì XOR không có thứ tự để chạy hai con trỏ như với tổng. Chỉ còn một chỗ tinh tế: ô gặp nhau thuộc cả hai nửa nếu ta tính nó ở cả hai phía.

Cùng cách nghĩ đó áp dụng cho hoán vị, xâu, đồ thị. Tìm đường đi ngắn nhất bằng BFS hai chiều là một dạng của nó: nếu mỗi trạng thái có $b$ trạng thái kề và đáp án cách $d$ bước, BFS từ hai đầu chỉ sinh cỡ $b^{d/2}$ trạng thái mỗi phía thay vì $b^d$ từ một phía.

Ví dụĐường Đi XOR Mục Tiêu

Đề. Bảng $n \times m$ ($n, m \le 20$), ô chứa số nguyên không âm tới $10^{18}$. Đếm đường đi từ $(1, 1)$ tới $(n, m)$, mỗi bước sang phải hoặc xuống dưới, có XOR các ô trên đường (kể cả hai đầu) bằng $K$.

Lời giải. Như vừa phân tích, có tới $3{,}5 \cdot 10^{10}$ đường nên không duyệt hết được, nhưng mọi đường cắt đường chéo $i + j = h$ tại đúng một ô. Chia mỗi đường thành nửa đầu từ $(0, 0)$ tới ô trên đường chéo và nửa sau từ ô đó tới $(n - 1, m - 1)$; hai nửa ghép được khi cùng ô gặp nhau và XOR của chúng bằng $K$.

Bước 1: nửa đầu. go1 đi từ $(0, 0)$, chỉ sang phải hoặc xuống, XOR dần các ô, kể cả ô gặp nhau. Tới ô có $i + j = h$ thì tăng cnt[i][v]: bảng đếm của ô gặp nhau ở hàng $i$ (hàng xác định luôn ô trên đường chéo).

void go1(ll i, ll j, ll v) {
    v ^= a[i][j];
    if (i + j == h) {
        cnt[i][v]++;
        return;
    }
    if (i + 1 < n) go1(i + 1, j, v);
    if (j + 1 < m) go1(i, j + 1, v);
}

Bước 2: nửa sau, đi ngược. go2 đi từ $(n - 1, m - 1)$ lên hoặc sang trái, XOR các ô trừ ô gặp nhau. Tới đường chéo với XOR $v$, nửa đầu cần XOR $v \oplus K$ để cả đường ra $K$, nên cộng cnt[i][v ^ K]. Quy ước ô gặp nhau chỉ thuộc nửa đầu là để ô ấy được XOR đúng một lần.

void go2(ll i, ll j, ll v) {
    if (i + j == h) {
        if (cnt[i].count(v ^ K)) ans += cnt[i][v ^ K];
        return;
    }
    v ^= a[i][j];
    if (i > 0) go2(i - 1, j, v);
    if (j > 0) go2(i, j - 1, v);
}

Với test ví dụ, hai đường đi qua $1, 2, 4, 16$ (theo hai cách) cho XOR 23.

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

ll n, m, K, h, ans, a[25][25];
map<ll, ll> cnt[25];

void go1(ll i, ll j, ll v) {
    v ^= a[i][j];
    if (i + j == h) {
        cnt[i][v]++;
        return;
    }
    if (i + 1 < n) go1(i + 1, j, v);
    if (j + 1 < m) go1(i, j + 1, v);
}

void go2(ll i, ll j, ll v) {
    if (i + j == h) {
        if (cnt[i].count(v ^ K)) ans += cnt[i][v ^ K];
        return;
    }
    v ^= a[i][j];
    if (i > 0) go2(i - 1, j, v);
    if (j > 0) go2(i, j - 1, v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> K;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < m; j++) cin >> a[i][j];
    h = (n + m - 2) / 2;
    go1(0, 0, 0);
    go2(n - 1, m - 1, 0);
    cout << ans << '\n';
}

Input2 3 23
1 2 4
8 4 16

Output2

Mỗi nửa đi tối đa 19 bước, tức cỡ $2^{19}$ nhánh, mỗi nhánh một thao tác map: khoảng $2^{19} \log 2^{19}$.