Universal Cup Judging System

Universal Cup

时间限制: 1.0 s 内存限制: 1024 MB 总分: 100
统计

Hay una cadena binaria $s_1$ de longitud $m$ almacenada en el disco #1.

Luego, se realizan $n - 1$ operaciones. En la $i$-ésima operación, se elige un disco $1 \le p_{i+1} \le i$, y la cadena $s_{p_{i+1}}$ de ese disco se copia al disco $i + 1$, produciendo $s_{i+1}$. Sin embargo, durante el proceso de copia, hasta $k$ bits pueden invertirse (es decir, ocurren errores en a lo sumo $k$ posiciones).

Se te dan todas las $n$ cadenas binarias finales $s_1, s_2, \dots, s_n$, cada una de longitud $m$. Tu tarea es determinar cuántas sucesiones posibles $p_2, p_3, \dots, p_n$ podrían dar lugar a esta configuración final.

Como la respuesta puede ser grande, solo necesitas hallar la respuesta módulo $998244353$.

Entrada

La primera línea de la entrada contiene tres enteros $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), descritos en el enunciado. Se garantiza que $m$ es múltiplo de $4$.

Cada una de las siguientes $n$ líneas contiene una cadena hexadecimal $s'_i$ de longitud $m/4$. Cada carácter de $s'_i$ es uno de 0–9 o A–F, donde $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.

Cada dígito en la representación hexadecimal $s'_i$ corresponde a cuatro bits consecutivos en la cadena binaria $s_i$. Específicamente, para cada dígito $s'_{i,j}$, se puede demostrar que existe una única tupla $(a, b, c, d)$ que satisface $s'_{i,j} = 8a + 4b + 2c + d$ y $a, b, c, d \in \{0, 1\}$. Los bits en la cadena binaria $s_i$ satisfacen $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.

Salida

Imprime un entero — el número de sucesiones válidas $(p_2, p_3, \dots, p_n)$ módulo $998244353$.

Ejemplo

5 8 2
95
05
BD
9C
BD
6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.