Codeforces Round 947 (Div. 1 + Div. 2) |
---|
Закончено |
Определим бинарное кодирование конечного множества целых неотрицательных чисел $$$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$$$, которые удовлетворяют следующим ограничениям:
Для экономии входные и выходные данные будут заданы в терминах двоичных кодировок множеств.
Первая строка содержит одно целое число $$$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$$$ в порядке возрастания.
315 15 15 15 15 15 12
4 3 5 6 7
563 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
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\}$$$ |
Название |
---|