P17125 [ICPC 2025 Shanghai R] Flower' s land 3

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

在磁盘 #1 上存储着一个长度为 $m$ 的二进制字符串 $s_1$。 随后，依次进行 $n - 1$ 次操作。在第 $i$ 次操作中，会选择一个磁盘 $1 \le p_{i+1} \le i$，将该磁盘上的字符串 $s_{p_{i+1}}$ 复制到磁盘 $i + 1$ 上，从而产生 $s_{i+1}$。然而，在复制过程中，最多可能有 $k$ 个比特发生翻转（即最多在 $k$ 个位置上出现错误）。 现在给定最终得到的全部 $n$ 个二进制字符串 $s_1, s_2, \cdots, s_n$，每个长度均为 $m$。你的任务是计算有多少种可能的序列 $p_2, p_3, \cdots, p_n$ 能够形成这样的最终局面。 由于答案可能很大，你只需要求出答案对 $998244353$ 取模的结果。

第一行包含三个整数 $n$，$m$，$k$ ($2 \le n \le 5000$，$4 \le m \le 15000$，$1 \le k \le 3$)，含义如题所述。保证 $m$ 是 $4$ 的倍数。 接下来 $n$ 行，每行包含一个长度为 $m/4$ 的十六进制字符串 $s_i'$。$s_i'$ 的每个字符均为 $0$–$9$ 或 $A$–$F$，其中 $A = 10$，$B = 11$，$\cdots$，$F = 15$。 十六进制表示 $s_i'$ 中的每一位对应二进制字符串 $s_i$ 中的连续 $4$ 个比特。具体而言，对于每一位 $s'_{i,j}$，可以证明存在唯一的四元组 $(a,b,c,d)$ 满足 $s'_{i,j} = 8a + 4b + 2c + d$ 且 $a,b,c,d \in \{0,1\}$。二进制字符串 $s_i$ 中的比特满足 $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a,b,c,d)$。

输出一个整数——合法的序列 $(p_2, p_3, \cdots, p_n)$ 的数量对 $998244353$ 取模的结果。

翻译由 DeepSeek V4 Pro 完成