← 返回题目列表

Codeforces · 1703/D

D. 双弦

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

给你 $$$n$$$ 个字符串 $$$s_1, s_2, \dots, s_n$$$,长度最多为 $$$\mathbf{8}$$$。

对于每个字符串 $$$s_i$$$,确定是否存在两个字符串 $$$s_j$$$ 和 $$$s_k$$$ 使得 $$$s_i = s_j + s_k$$$。也就是说,$$$s_i$$$ 是$$$s_j$$$ 和$$$s_k$$$ 的串联。请注意,$$$j$$$ 可以等于 $$$k$$$。

回想一下,字符串 $$$s$$$ 和 $$$t$$$ 的串联是 $$$s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$$$,其中 $$$p$$$ 和 $$$q$$$ 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。例如,“code”和“forces”的串联是“codeforces”。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 字符串的数量。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含非空字符串 $$$s_i$$$,长度最多为 $$$\mathbf{8}$$$,由小写英文字母组成。在给定的 $$$n$$$ 字符串中,可能存在相等(重复)。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串。如果存在两个字符串 $$$s_j$$$ 和 $$$s_k$$$,其中 $$$s_i = s_j + s_k$$$,则第 $$$i$$$ 位应为 $$$\texttt{1}$$$,否则为 $$$\texttt{0}$$$。请注意,$$$j$$$ 可以等于 $$$k$$$。

示例

输入 #1

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code

输出 #1

10100
011
10100101

注意

在第一个测试用例中,我们有以下内容:

- $$$s_1 = s_2 + s_2$$$,因为 $$$\texttt{abab} = \texttt{ab} + \texttt{ab}$$$。请记住,$$$j$$$ 可以等于 $$$k$$$。
- $$$s_2$$$ 不是列表中任何两个字符串的串联。
- $$$s_3 = s_2 + s_5$$$,因为 $$$\texttt{abc} = \texttt{ab} + \texttt{c}$$$。
- $$$s_4$$$ 不是列表中任何两个字符串的串联。
- $$$s_5$$$ 不是列表中任何两个字符串的串联。