It's Mobius time - DP SOS

Cho $n$ số $a_1, \dots, a_n$. Với mỗi $s$ từ $1$ đến $2^{20}$ đếm số tập con mà AND của các phần tử bằng đúng $s$.

Giới hạn: $1 \le n \le 2^{20}, 0 \le a_i \le 2^{20}$.

Tương tự, gọi $f(s)$ là đáp án với $s$ cố định, ta định nghĩa $g(s)$ là số tập con có AND là một super-mask của $s$ (giống với quan hệ chia hết). Khi này ta có $g(s) = \sum_{s’ \subseteq s} f(s’)$ và $f(s) = \mu(g(s)) = \sum_{s' \subseteq s}(-1)^{|s \setminus s’|} g(s’)$.

Để tập con có AND là super-mask của $s$ thì từng số trong dãy phải là super-mask của $s$. Gọi $\text{cnt}(s)$ là số lần xuất hiện của $s$, thì $h(s) = z(\text{cnt}(s))$ chính là số số trong dãy là super-mask của $s$. Như vậy ta có $g(s) = 2^{h(s)}$. Qua implementation ở trên ta tính lại được $f(s)$ hiệu quả trong $O(n \log n)$.

Code: https://codeforces.com/contest/449/submission/305550830.

Cho tập $S$ gồm $n$ xâu kí tự $s_1, s_2, \dots, s_n$. Các kí tự trong tất cả các xâu này đều được sắp xếp. Ta định nghĩa $f(T)$ với một tập xâu $T$ là số xâu mà là xâu con của ít nhất một xâu trong $T$.

Tính $f(T)$ với mọi $T \subseteq S$.

Giới hạn: $1 \le n \le 23, 1 \le |s_i| \le 2 \times 10^4$.

Với các bài toán ta cần đếm số cấu hình thoả mãn ít nhất một/tất cả/vài điều kiện, điều đầu tiên có thể nghĩ đến là bao hàm loại trừ.

Với mỗi xâu $s_i$ ta có tập xâu con $\text{sub}_i$ tương ứng của nó. Ta có

Bằng bao hàm loại trừ, ta có thể đưa việc tính tổng hợp về tính tổng giao, và tính tổng giao này thường sẽ có công thức tổng quát. Hay nói cách khác, khi biến đổi SOS xuôi $f \rightarrow g$, $f$ khó tính được trực tiếp, nhưng $g$ thì khả năng cao là tính được, rồi ta SOS ngược để tính $f$.

Từ giả thiết, không khó để ta viết ra được công thức sau:

với $\text{cnt}_{\text{ch}}$ là số lần xuất hiện của kí tự $\text{ch}$ trong các xâu thuộc $T$.

Vì mỗi kí tự từ a đến z đóng góp độc lập nhau nên ta có thể tính đóng góp của từng kí tự một rồi nhân các kết quả lại để tối ưu bộ nhớ. (chỉ cần $O(2^n)$ thay vì $O(2^n \times 26)$.

Đây cũng là phần ta cần lưu ý. Khi tính $g(T)$ theo từng kí tự một, thì khi này thao tác khi áp dụng SOS là phép lấy min. Với các phép toán idempotent (luỹ đẳng, như min, max, gcd, lcm, AND, OR, etc), ta chỉ cần lấy 1 submask để cập nhật kết quả, chứ không phải duyệt toàn bộ. Với phép lấy min thì ta chỉ cần $O(1)$ để cập nhật trạng thái ở mỗi mask. Nên với bước này ta chỉ mất $O(2^n(n + A)).$

Có $g$ rồi thì ta SOS ngược để tính $f$. Tổng độ phức tạp cuối cùng là $O(2^n(N + A))$, bộ nhớ là $O(2^n)$.

Code: Submission #305505198 - Codeforces

Cho 1 tập $A$ gồm $n$ số. Ta định nghĩa bao đóng AND-OR của tập $A$ là cách thêm ít phần tử nhất vào $A$ sao cho:

1. Với $x, y \in A$ thì $x \ \& \ y \in A$.

2. Với $x, y \in A$ thì $x \ | \ y \in A$.

Tìm kích thước bao đóng AND-OR của $A$.

Giới hạn: $1 \le n \le 10^5, 1 \le a_i \le 2^{40}$.

Trong bài toán này ta cần tìm cách mô tả cấu trúc của bao đóng $B$ thay vì mô phỏng.

Bước 1: Lược bỏ bit.

1. Nếu một bit có cùng giá trị ở mọi phần tử của $A$ thì giá trị đó được giữ nguyên qua mọi phép AND, OR. Ta loại bỏ các bit này.

2. Nếu hai bit bằng nhau ở mọi phần tử của $A$ thì chúng cũng bằng nhau ở mọi phần tử của $B$. Ta gộp chúng thành một bit.

Sau bước này còn lại $k \le 40$ bit.

Bước 2: Quy về đếm antichain.

Ta viết $i \to j$ nếu mọi phần tử của $A$ có bit $i$ đều có bit $j$. Sau bước 1, quan hệ $\to$ có tính phản xạ, bắc cầu và phản đối xứng, tức là tạo ra một thứ tự bộ phận (poset) trên tập bit. Đặt $u_i$ là AND của các phần tử có bit $i$; khi đó bit $j$ thuộc $u_i$ khi và chỉ khi $i \to j$.

Coi mỗi số là tập các bit bật của nó. Ta gọi tập bit $C$ là đóng nếu từ $i \in C$ và $i \to j$ suy ra $j \in C$.

Mỗi tập đóng $C$ được xác định duy nhất bởi tập $S$ gồm các bit $i \in C$ không bị kéo theo bởi bit nào khác của $C$, vì $C = \bigcup_{i \in S} u_i$. Tập $S$ là một antichain: các bit trong $S$ đôi một không so sánh được. Ngược lại, mỗi antichain $S$ sinh ra đúng một tập đóng. Vậy đáp án bằng số antichain (kể cả antichain rỗng) của một thứ tự bộ phận trên $k$ phần tử.

Bước 3: Đếm antichain bằng chia đôi tập và SOS.

Ta chia $k$ bit thành hai nửa: $L$ gồm $h = \lfloor k/2 \rfloor$ bit và $R$ gồm $r = k - h$ bit. Mỗi antichain $S$ tương ứng với một cặp $(S_L, S_R)$, trong đó $S_L, S_R$ lần lượt là antichain của $L$ và $R$, và không có bit nào của $S_L$ so sánh được với bit nào của $S_R$.

1. Với mỗi antichain $S_L$, gọi $\text{free}(S_L) \subseteq R$ là tập các bit của $R$ không so sánh được với bit nào của $S_L$. Điều kiện ghép cặp là $S_R \subseteq \text{free}(S_L)$.

2. Gọi $\text{cnt}(T)$ là số antichain $S_L$ có $\text{free}(S_L) = T$. Số antichain của $L$ ghép được với $S_R$ là $F(S_R) = \sum_{T \supseteq S_R} \text{cnt}(T)$. Đây chính là biến đổi Zeta, chỉ khác là lấy tổng trên các tập cha thay vì tập con.

3. Đáp án là $\sum_{S_R} F(S_R)$, lấy trên mọi antichain $S_R$ của $R$.

Các antichain của mỗi nửa được duyệt bằng DP trên mask: mask $m$ là antichain khi và chỉ khi mask $m$ bỏ đi bit thấp nhất $i$ là antichain và bit $i$ không so sánh được với phần còn lại. Giá trị $\text{free}(m)$ cũng được cập nhật từ mask bỏ bit thấp nhất. Mỗi mask chỉ tốn $O(1)$.

Độ phức tạp: $O(n \log V)$ để tính các $u_i$, $O(k^2)$ để dựng quan hệ và $O(k \cdot 2^{k/2})$ cho bước chia đôi cùng SOS, với $V = 2^{40}$ và $k \le 40$. Bộ nhớ $O(n + 2^{k/2})$.

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7

8
    const int B = 41;  // a_i <= 2^40
9
    int n;
10
    cin >> n;
11
    vector<long long> a(n);
12
    for (auto& x : a) cin >> x;
13

14
    // up[b]: AND of every number that has bit b; bit c is in up[b] iff b -> c
15
    vector<long long> up(B, -1);
16
    vector<int> cnt(B, 0);
17
    for (long long x : a)
18
        for (int b = 0; b < B; b++)
19
            if (x >> b & 1) cnt[b]++, up[b] &= x;
20

21
    // keep the bits that are not constant, one per class of equal bits
22
    vector<int> bits;
23
    for (int b = 0; b < B; b++) {
24
        if (cnt[b] == 0 || cnt[b] == n) continue;
25
        bool twin = false;
26
        for (int c : bits) twin |= (up[c] >> b & 1) && (up[b] >> c & 1);
27
        if (!twin) bits.push_back(b);
28
    }
29

30
    // count the antichains of the poset on these bits
31
    int k = bits.size(), h = k / 2, r = k - h;
32
    auto le = [&](int i, int j) { return up[bits[i]] >> bits[j] & 1; };
33
    vector<int> clash1(h, 0), free2(h, (1 << r) - 1), clash2(r, 0);
34
    for (int i = 0; i < k; i++)
35
        for (int j = 0; j < k; j++) {
36
            if (i == j || !(le(i, j) || le(j, i))) continue;
37
            if (i < h && j < h) clash1[i] |= 1 << j;
38
            if (i < h && j >= h) free2[i] &= ~(1 << (j - h));
39
            if (i >= h && j >= h) clash2[i - h] |= 1 << (j - h);
40
        }
41

42
    // first half: for each antichain, the second-half bits still allowed with it
43
    vector<long long> f(1 << r, 0);
44
    vector<int> ok(1 << h), allowed(1 << h);
45
    ok[0] = 1, allowed[0] = (1 << r) - 1;
46
    f[allowed[0]]++;
47
    for (int m = 1; m < (1 << h); m++) {
48
        int i = __builtin_ctz(m), rest = m & (m - 1);
49
        ok[m] = ok[rest] && !(clash1[i] & rest);
50
        allowed[m] = allowed[rest] & free2[i];
51
        if (ok[m]) f[allowed[m]]++;
52
    }
53

54
    // superset sums: f[s] = number of first-half antichains that allow all of s
55
    for (int i = 0; i < r; i++)
56
        for (int m = 0; m < (1 << r); m++)
57
            if (!(m >> i & 1)) f[m] += f[m | 1 << i];
58

59
    // second half: pair each antichain with the first-half ones that allow it
60
    vector<int> ok2(1 << r);
61
    ok2[0] = 1;
62
    long long ans = f[0];
63
    for (int m = 1; m < (1 << r); m++) {
64
        int i = __builtin_ctz(m), rest = m & (m - 1);
65
        ok2[m] = ok2[rest] && !(clash2[i] & rest);
66
        if (ok2[m]) ans += f[m];
67
    }
68
    cout << ans << '\n';
69
}