AT_agc024_f.[AGC024F] Simple Subsequence Problem

给定一个由 0 和 1 组成的字符串集合 $S$ 以及一个整数 $K$。请你求出作为 $S$ 中至少 $K$ 个不同字符串的子序列的最长字符串。如果有多个满足条件的字符串，输出字典序最小的那个。

集合 $S$ 的给定方式如下：

• 给定整数 $N$ 和 $N+1$ 个字符串，这 $N+1$ 个字符串依次为 $X_0, X_1, ..., X_N$，其中每个 $X_i$ 的长度为 $2^i$。
• 对于任意整数对 $(i, j)$（$0 \leq i \leq N, 0 \leq j < 2^i$），$X_i$ 的第 $j$ 个字符（第一个字符为第 $0$ 个，最后一个为第 $2^i-1$ 个）为 1 当且仅当，将 $j$ 用 $i$ 位二进制表示（必要时在前面补 $0$），得到的字符串属于 $S$。
• 长度大于等于 $N+1$ 的字符串不属于 $S$。

此外，字符串 $A$ 是字符串 $B$ 的子序列，指存在整数序列 $t_1 < t_2 < ... < t_{|A|}$，使得对于所有 $i(1 \leq i \leq |A|)$，$A$ 的第 $i$ 个字符等于 $B$ 的第 $t_i$ 个字符。

输入通过标准输入给出，格式如下：

$N$ $K$ $X_0$ $:$ $X_N$

请输出作为 $S$ 中至少 $K$ 个不同字符串的子序列的最长字符串中，字典序最小的那个。

限制条件

• $0 \leq N \leq 20$
• $X_i (0 \leq i \leq N)$ 的长度为 $2^i$，且仅包含 0 和 1
• $1 \leq K \leq |S|$
• $K$ 是整数

样例解释 1

$S$ 中的字符串有（空字符串）、1、00、10、11、001、100、101、110。这些字符串中，作为至少 $4$ 个字符串的子序列的最长且字典序最小的字符串是 10。

样例解释 3

答案为空字符串。

由 ChatGPT 4.1 翻译