← 返回题目列表

Codeforces · 1975/F

F. 设置

中文机器翻译题面 查看原题

将有限自然数集 $$$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$$$ 行中,您应该按升序输出所有可能的 $$$S$$$ $$$f(S)$$$。

示例

输入 #1

3
15 15 15 15 15 15 12

输出 #1

4
3
5
6
7

输入 #2

5
63 63 63 63 6 63 63 63 63 63 63 5 63 63 63 63 63 63 8 63 63 63 63 2 63 63 63 63 63 63 63

输出 #2

1
19

注意

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

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