Universal Cup Judging System

Universal Cup

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

Det finns en binär sträng $s_1$ av längd $m$ lagrad på disk #1.

Därefter utförs $n - 1$ operationer. I den $i$-te operationen väljs en disk $1 \le p_{i+1} \le i$, och strängen $s_{p_{i+1}}$ på den disken kopieras till disk $i + 1$, vilket ger $s_{i+1}$. Under kopieringsprocessen kan dock upp till $k$ bitar inverteras (dvs. fel uppstår på högst $k$ positioner).

Du får alla de slutliga $n$ binära strängarna $s_1, s_2, \dots, s_n$, var och en av längd $m$. Din uppgift är att bestämma hur många möjliga följder $p_2, p_3, \dots, p_n$ som skulle kunna resultera i denna slutliga konfiguration.

Eftersom svaret kan vara stort behöver du bara hitta svaret modulo $998244353$.

Indata

Den första raden i indatan innehåller tre heltal $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), som beskrivs i uppgiften. Det garanteras att $m$ är en multipel av $4$.

Var och en av de följande $n$ raderna innehåller en hexadecimal sträng $s'_i$ av längd $m/4$. Varje tecken i $s'_i$ är ett av 0–9 eller A–F, där $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.

Varje siffra i den hexadecimala representationen $s'_i$ motsvarar fyra på varandra följande bitar i den binära strängen $s_i$. Mer specifikt kan det för varje siffra $s'_{i,j}$ bevisas att det finns en unik tupel $(a, b, c, d)$ som uppfyller $s'_{i,j} = 8a + 4b + 2c + d$ och $a, b, c, d \in \{0, 1\}$. Bitarna i den binära strängen $s_i$ uppfyller $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.

Utdata

Skriv ut ett heltal — antalet giltiga följder $(p_2, p_3, \dots, p_n)$ modulo $998244353$.

Exempel

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.