4287. [THUPC 2025 Final] Now or Never

【题目描述】

对于一个长度为 $l$ 的 01 串 $w=w_1w_2\dots w_l$，定义其支撑序列 $\mathrm{supp}(w)$ 为 $[1, 2, \dots, l]$ 的一个子序列，其中 $i\in \mathrm{supp}(w)$ 当且仅当 $w_i = 1$。例如，$\mathrm{supp}(001100110) = [3, 4, 7, 8]$。特别地，全零串的支撑序列为空序列 $\varepsilon$。

给定一个 01 串集合 $S$，其中包含 $n$ 个长度为 $m$ 的 01 串 $s_1, s_2, \dots, s_n$。再给定 $q$ 组询问，第 $i$ 组询问给出一个长度为 $m$ 的 01 串 $t_i$。你需要输出一个长度为 $m$ 的 01 串 $u_i$ 满足以下条件：

1. 存在一个 $S$ 的子集 $T$，其中 $T$ 可以为空也可以为 $S$ 本身，满足 $u_i = t_i \oplus \left(\bigoplus_{v \in T} v \right)$，其中 $\oplus$ 表示按位异或操作，即 $u_i$ 为 $t_i$ 与 $T$ 中所有 01 串的异或和；
2. 在以上条件的基础之上，$u_i$ 的支撑序列的字典序尽可能小。

对于两个序列 $A, B$，称 $A$ 的字典序小于 $B$，当且仅当 $A$ 是 $B$ 的一个真前缀，或者 $A$ 和 $B$ 在第一个相异的位置 $p$ 上满足 $A_p < B_p$。

【输入格式】

输入的第一行三个正整数 $n, m, q\ (1\le n, m, q\le 2000)$，分别表示集合 $S$ 的大小、01 串的长度以及询问组数。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的 01 串 $s_i$。

最后 $q$ 行，第 $i$ 行一个长度为 $m$ 的 01 串 $t_i$ 描述一组询问。

【输出格式】

对于第 $i$ 组询问输出一行表示满足题设条件的长度为 $m$ 的 01 串 $u_i$。

【输入样例 1】

1 3 2
110
010
101

【输出样例 1】

100
101

【样例解释 1】

对于第一组测试数据，满足第一个条件的串有 010 和 100。二者支撑序列分别为 $\mathrm{supp}(010) = [2]$，$\mathrm{supp}(100) = [1]$，其中字典序更小的是 $[1]$。

对于第二组测试数据，满足第一个条件的串有 101 和 011。二者支撑序列分别为 $\mathrm{supp}(101) = [1, 3]$，$\mathrm{supp}(011) = [2, 3]$，其中字典序更小的是 $[1, 3]$。

【输入样例 2】

2 4 4
1100
1010
1000
0001
0110
0011

【输出样例 2】

1000
1101
0000
1111

【样例解释 2】

对于第一组测试数据，满足第一个条件的串有 1000、0100、0010 和 1110，其中字典序最小的支撑序列是 $\mathrm{supp}(1000) = [1]$。

对于第二组测试数据，满足第一个条件的串有 0001、1101、1011 和 0111，其中字典序最小的支撑序列是 $\mathrm{supp}(1101) = [1, 2, 4]$。

对于第三组测试数据，满足第一个条件的串有 0110、1010、1100 和 0000，其中字典序最小的支撑序列是 $\mathrm{supp}(0000) = \varepsilon$，也即空序列。

对于第四组测试数据，满足第一个条件的串有 0011、1111、1001 和 0101，其中字典序最小的支撑序列是 $\mathrm{supp}(1111) = [1, 2, 3, 4]$。

【样例输入 3】

3 9 7
011001111
101110001
110010100
010110110
101010100
000101101
001011100
100011111
100111000
001000101

【样例输出 3】

111101101
110110001
110111001
111100010
111111010
111110111
111111011

【样例输入 4】

9 24 9
100001011101000000000000
100011001100100001000000
010101000010100111110100
101110000010101110110010
100110110010011100000000
111111000010100101111011
000010110001001011010101
010101100111000010100111
111001111111000000000000
111000110110110000000000
011100101000100001000000
101001101000111011001100
100011100011110001000000
100001001011000000000000
101110110001111100000000
100011100101100010110000
101001001100101011000000
100101100110100111000000

【样例输出 4】

111111111100001001010011
111111101111001101010101
111111101100001011000101
111111101101110101111011
111111111111000010111011
111111111111110101011010
111111101110101001001101
111111101101111110011010
111111111110100001000000

【来源】

清华大学学生算法协会 GitLink 仓库