CF1975F.Set

定义有限自然数集合 $T \subseteq \{0,1,2,\ldots\}$ 的二进制编码为 $f(T) = \sum\limits_{i \in T} 2^i$。例如，$f(\{0,2\}) = 2^0 + 2^2 = 5$，$f(\{\}) = 0$。注意，$f$ 是从所有这样的集合到所有非负整数的双射，因此 $f^{-1}$ 也是定义良好的。

给定一个整数 $n$ 以及 $2^n-1$ 个集合 $V_1,V_2,\ldots,V_{2^n-1}$。

请找出所有满足以下约束的集合 $S$：

• $S \subseteq \{0,1,\ldots,n-1\}$，注意 $S$ 可以为空集。
• 对于所有非空子集 $T \subseteq \{0,1,\ldots,n-1\}$，都有 $|S \cap T| \in V_{f(T)}$。

由于输入输出规模较大，输入和输出均以集合的二进制编码形式给出。

第一行包含一个整数 $n$（$1 \leq n \leq 20$）。

第二行包含 $2^n-1$ 个整数 $v_1,v_2,\ldots,v_{2^n-1}$（$0 \leq v_i < 2^{n+1}$），表示集合 $V_i$ 的二进制编码，其中 $V_i = f^{-1}(v_i)$。

第一行输出一个整数 $k$，表示满足条件的 $S$ 的个数。

接下来的 $k$ 行，每行输出一个 $f(S)$，按升序排列所有可能的 $S$。

在第一个测试用例中，一个可能的 $S$ 是 $f^{-1}(3) = \{0,1\}$。所有非空子集 $T \subseteq \{0,1,2\}$ 及其对应的 $|S \cap T|$、$f(T)$ 和 $V_{f(T)}$ 如下：

$$\begin{aligned} T &\quad |S\cap T| &\quad f(T) &\quad V_{f(T)} \\ \{0\} &\quad 1 &\quad 1 &\quad \{0,1,2,3\} \\ \{1\} &\quad 1 &\quad 2 &\quad \{0,1,2,3\} \\ \{2\} &\quad 0 &\quad 4 &\quad \{0,1,2,3\} \\ \{0,1\} &\quad 2 &\quad 3 &\quad \{0,1,2,3\} \\ \{0,2\} &\quad 1 &\quad 5 &\quad \{0,1,2,3\} \\ \{1,2\} &\quad 1 &\quad 6 &\quad \{0,1,2,3\} \\ \{0,1,2\} &\quad 2 &\quad 7 &\quad \{2,3\} \\ \end{aligned}$$

由 ChatGPT 4.1 翻译