Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 1024 MB 總分: 100
统计

Auf Festplatte #1 ist eine Binärzeichenkette $s_1$ der Länge $m$ gespeichert.

Anschließend gibt es $n - 1$ Operationen. In der $i$-ten Operation wird eine Festplatte $1 \le p_{i+1} \le i$ ausgewählt und die Zeichenkette $s_{p_{i+1}}$ auf dieser Festplatte wird auf Festplatte $i + 1$ kopiert, wodurch $s_{i+1}$ entsteht. Während des Kopiervorgangs können jedoch bis zu $k$ Bits invertiert werden (d. h., es treten an höchstens $k$ Positionen Fehler auf).

Dir sind alle endgültigen $n$ Binärzeichenketten $s_1, s_2, \dots, s_n$ gegeben, jede der Länge $m$. Deine Aufgabe ist es zu bestimmen, wie viele mögliche Folgen $p_2, p_3, \dots, p_n$ zu dieser Endkonfiguration führen könnten.

Da die Antwort groß sein kann, musst du nur die Antwort modulo $998244353$ bestimmen.

Eingabe

Die erste Zeile der Eingabe enthält drei ganze Zahlen $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), wie in der Aufgabenstellung beschrieben. Es wird garantiert, dass $m$ ein Vielfaches von $4$ ist.

Jede der nächsten $n$ Zeilen enthält eine hexadezimale Zeichenkette $s'_i$ der Länge $m/4$. Jedes Zeichen von $s'_i$ ist eines aus 0–9 oder A–F, wobei $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$ gilt.

Jede Stelle in der hexadezimalen Darstellung $s'_i$ entspricht vier aufeinanderfolgenden Bits in der Binärzeichenkette $s_i$. Genauer gesagt lässt sich für jede Stelle $s'_{i,j}$ beweisen, dass ein eindeutiges Tupel $(a, b, c, d)$ existiert, das $s'_{i,j} = 8a + 4b + 2c + d$ und $a, b, c, d \in \{0, 1\}$ erfüllt. Die Bits in der Binärzeichenkette $s_i$ erfüllen $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.

Ausgabe

Gib eine ganze Zahl aus — die Anzahl der gültigen Folgen $(p_2, p_3, \dots, p_n)$ modulo $998244353$.

Beispiel

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.