Closed Subsets#12414

Closed Subsets (Editorial)

Problem Author:	turneja
Prepared by:	turneja
Edited by:	turneja

Solution

The answer is the sum of $f (x, y)$ f(x,y) where $f (x, y)$ f(x,y) is the number of subsets for which the following holds:

the subset contains at least one occurrence of value $x$ ,
the subset contains at least one occurrence of value $y$ ,
all chosen elements $a$ satisfy $x \subseteq a \subseteq y$ x \subseteq a \subseteq y ( $a$ must be a supermask of $x$ and a submask of $y$ ).

It is a known result that $\sum_{x = 0}^{2^{m} - 1} # {s ∣ s \subseteq x} = \sum_{x = 0}^{2^{m} - 1} 2^{popcount (x)} = 3^{m}$ \sum_{x=0}^{2^{m}-1} \#\{\, s \mid s \subseteq x \,\} = \sum_{x=0}^{2^{m}-1} 2^{\mathrm{popcount}(x)} = 3^{m}, or the sum of the number of submasks of all integers from $0$ to $2^{m} - 1$ 2^m - 1 is equal to $3^{m}$ 3^m. Therefore a feasible solution can calculate each possible value $f (x, y)$ f(x,y) explicitely and add it to the solution.

Let us fix $y$ , or the bitwise OR of the subset and calculate $f (x, y)$ f(x,y) for each $x$ which is a submask of the fixed $y$ . Let $d p [z] = \sum_{a : z \subseteq a \subseteq y} freq [a]$ dp[z] = \sum_{a:\; z \subseteq a \subseteq y} \mathrm{freq}[a]. These values can be calculated quickly with a sum over subsets/superset zeta transform algorithm but only iterating over the submasks of $y$ instead of all possible integers.

Then finally $f (x, y)$ f(x,y) can be calculated as $f (x, y) = ⎩ ⎨ ⎧ 2^{freq [x]} - 1, (2^{freq [x]} - 1) (2^{freq [y]} - 1) \cdot 2^{d p [x] - freq [x] - freq [y]}, x = y, x \neq = y,$ f(x,y)= \begin{cases} 2^{\mathrm{freq}[x]}-1, & x=y,\\[6pt] \left(2^{\mathrm{freq}[x]}-1\right)\left(2^{\mathrm{freq}[y]}-1\right)\cdot 2^{\,dp[x]-\mathrm{freq}[x]-\mathrm{freq}[y]}, & x\ne y, \end{cases}

The time complexity will be $O (m 3^{m})$ \mathcal{O}(m3^{m}) where $m$ is the maximum of most significant bit of the input integers.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int N = 1e5 + 5;
const ll M = 998244353;

int freq[N];
int dp[N];
ll pw[N];

int main() {
    IOS;
    pw[0] = 1;
    for (int i = 1; i < N; i++) {
        pw[i] = pw[i - 1] * 2 % M;
    }
    int n, mx = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        freq[a]++;
        mx = max(mx, a);
    }
    int b = 0, p = 1;
    while (mx >= p) {
        b++;
        p *= 2;
    }
    ll ans = 0;
    for (int i = 1; i <= mx; i++) {
        if (!freq[i]) {
            continue;
        }
        for (int j = i; j > 0; j = (j - 1) & i) {
            dp[j] = freq[j];
        }
        for (int k = 0; k < b; k++) {
            int c = (1 << k) & i;
            if (!c) {
                continue;
            }
            for (int j = i; j > 0; j = (j - 1) & i) {
                int c = (1 << k) & j;
                if (!c) {
                    dp[j] += dp[j ^ (1 << k)];
                }
            }
        }
        for (int j = i; j > 0; j = (j - 1) & i) {
            if (j == i) {
                ans = (ans + pw[freq[j]] - 1 + M) % M;
            } else {
                ans = (ans + (pw[freq[j]] - 1) * (pw[dp[j] - freq[j] - freq[i]]) % M * (pw[freq[i]] - 1)) % M;
            }
        }
    }
    cout << ans;




    return 0;
}

C++