#P18657. The Best Problem of 2021
The Best Problem of 2021
The Best Problem of 2021
那是2021年。人们仍在关注新冠疫情,NNSU刚赢得ICPC 2020,我们正在为SnackDown决赛寻找题目,7dan提出了这道题。我们当时没有采用它,但在内部一直把它称为“The Best Problem of 2021”。
给定一个由整数构成的数组 和一个整数 。求集合 的子集 中,有多少个满足:把整数视为 上的向量、把按位异或(XOR)视为向量加法时, 是 的一组基。答案对 取模。
这里,若数组 能使 中每个元素都表示成 中若干元素的按位异或,并且 的长度是所有具有这种性质的数组中最小的,则称 是 的一组基。
注意,题意没有要求 中的元素本身属于 。例如第三组样例中,基数组包含大于 的整数。
输入格式
第一行两个整数 (),分别表示数组 的长度和所有整数的二进制位数。
接下来 行,每行一个长度恰好为 的二进制字符串,表示 的一个元素。
最后一行一个长度恰好为 的二进制字符串,表示 。
这些二进制表示允许有前导零。输入没有保证 线性无关; 也可以为零,此时 为空集。
输出格式
输出符合条件的子集数量对 取模的结果。
样例输入 1
4 4
0001
0010
0100
1000
1101
样例输出 1
7364
样例输入 2
3 2
00
00
00
11
样例输出 2
0
样例输入 3
2 3
110
101
101
样例输出 3
1
样例输入 4
3 10
1111100110
0011110100
0101100001
1110000001
样例输出 4
38