题解：CF1975F Set

喵仔牛奶 · 2024-07-04 19:06:48 · 题解

神仙题，看了好久题解才看懂，那就来写一篇比较详细的题解并给出一个较为简洁的实现吧 qwq

我们记 s=f(S),S=f^{-1}(s)，即小写字母表示集合转化后得到的数，大写字母表示集合。记 \land 表示按位与，即 C++ 中的 &。

题目里面 T\neq\emptyset 的限制不太符合常理，我们先把这个限制解除。由于 \lvert S\cap \emptyset\rvert=0，所以令 v_0=1 即可。下文不再有该限制。

观察 S 合法的条件：

我们考虑把 t 的 2^{n-1} 这位拆出来，条件变为：

分讨 S 中是否有 (n-1)：

• 若有，则第二个条件变为 \lvert S\cap f^{-1}(t)\rvert+1\in f^{-1}(v_{t+2^{n-1}})，即 \lvert S\cap f^{-1}(t)\rvert\in f^{-1}(\lfloor\frac{v_{t+2^{n-1}}}{2}\rfloor)。联立第一个条件得到 \lvert S\cap f^{-1}(t)\rvert\in f^{-1}(v_t)\cap f^{-1}(\lfloor\frac{v_{t+2^{n-1}}}{2}\rfloor)，也就是： \forall t\in[0,2^{n-1}),\lvert S\cap f^{-1}(t)\rvert\in f^{-1}(v_t\land \lfloor\frac{v_{t+2^{n-1}}}{2}\rfloor)
• 若没有，第二个条件变为 \lvert S\cap f^{-1}(t)\rvert\in f^{-1}(v_{t+2^{n-1}})，联立第一个条件得 \forall t\in[0,2^{n-1}),\lvert S\cap f^{-1}(t)\rvert\in f^{-1}(v_t\land v_{t+2^{n-1}})

对照最前面 S 合法的条件，我们发现我们已经将原问题分解为了两个规模为 2^{n-1} 的子问题，递归下去即可解决。当 n=0 时，\lvert S\cap f^{-1}(t)\rvert=0，若此时 v_t\bmod 2=1 就有 S 合法。

至于实现，我们可以不真地递归下去，而是从 (n-1) 到 0 枚举 k，对每个 k 枚举形如 [0,2^k),[2^k,2\times2^k),[2\times 2^k,3\times 2^k),\cdots 的区间分成两半即可。具体实现见代码，非常简洁。

时间复杂度 \mathcal{O}(n2^n)。

参考代码：

... //  下文 REP(i, l, r) 表示从 l 到 r 枚举 i
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 2e6 + 5;
    int n, ct, v[N];
    int main() {
        cin >> n, v[0] = 1; // 去除 T 不为空的限制
        REP(i, 1, (1 << n) - 1) cin >> v[i];
        for (int k = 1 << (n - 1); k; k >>= 1) // 长度为 2k 的区间分成前后长度为 k 的两半
            REP(i, 0, (1 << n) - 1) {
                if (i & k) continue; // 是否在区间中的前一半，若在后一半则跳过
                int x = v[i], y = v[i + k];
                v[i] = x & y, v[i + k] = x & y >> 1; // 同时处理前后两半中对应的数
            }
        REP(i, 0, (1 << n) - 1) ct += v[i] & 1;
        cout << ct << '\n';
        REP(i, 0, (1 << n) - 1)
            if (v[i] & 1) cout << i << '\n';
        return 0;
    }
}