#P18657. The Best Problem of 2021

    ID: 17993 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTSGF(2) 消元偏序集莫比乌斯反演高斯二项式系数计数 DP滚动数组位压缩存储

The Best Problem of 2021

The Best Problem of 2021

那是2021年。人们仍在关注新冠疫情,NNSU刚赢得ICPC 2020,我们正在为SnackDown决赛寻找题目,7dan提出了这道题。我们当时没有采用它,但在内部一直把它称为“The Best Problem of 2021”。

给定一个由整数构成的数组 BB 和一个整数 XX。求集合 {1,2,…,X}\{1,2,\ldots,X\} 的子集 SS 中,有多少个满足:把整数视为 Z2\mathbb Z_2 上的向量、把按位异或(XOR)视为向量加法时,BB 是 SS 的一组基。答案对 998244353998244353 取模。

这里,若数组 BB 能使 SS 中每个元素都表示成 BB 中若干元素的按位异或,并且 BB 的长度是所有具有这种性质的数组中最小的,则称 BB 是 SS 的一组基。

注意,题意没有要求 BB 中的元素本身属于 SS。例如第三组样例中,基数组包含大于 XX 的整数。

输入格式

第一行两个整数 n,mn,m(1≤n,m≤20001\le n,m\le2000),分别表示数组 BB 的长度和所有整数的二进制位数。

接下来 nn 行,每行一个长度恰好为 mm 的二进制字符串,表示 BB 的一个元素。

最后一行一个长度恰好为 mm 的二进制字符串,表示 XX。

这些二进制表示允许有前导零。输入没有保证 BB 线性无关;XX 也可以为零,此时 {1,…,X}\{1,\ldots,X\} 为空集。

输出格式

输出符合条件的子集数量对 998244353998244353 取模的结果。

样例输入 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