Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100
統計

Det er lagret en binær streng $s_1$ med lengde $m$ på disk #1.

Deretter utføres det $n - 1$ operasjoner. I den $i$-te operasjonen velges en disk $1 \le p_{i+1} \le i$, og strengen $s_{p_{i+1}}$ på denne disken kopieres til disk $i + 1$, noe som gir $s_{i+1}$. Under kopieringsprosessen kan imidlertid opptil $k$ biter bli snudd (dvs. at det oppstår feil i høyst $k$ posisjoner).

Du får oppgitt alle de $n$ endelige binære strengene $s_1, s_2, \dots, s_n$, hver med lengde $m$. Din oppgave er å bestemme hvor mange mulige følger $p_2, p_3, \dots, p_n$ som kan resultere i denne endelige konfigurasjonen.

Siden svaret kan være stort, trenger du bare å finne svaret modulo $998244353$.

Inndata

Den første linjen i inndataene inneholder tre heltall $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), som beskrevet i oppgaveteksten. Det er garantert at $m$ er et multiplum av $4$.

Hver av de neste $n$ linjene inneholder en heksadesimal streng $s'_i$ med lengde $m/4$. Hvert tegn i $s'_i$ er ett av 0–9 eller A–F, der $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.

Hvert siffer i den heksadesimale representasjonen $s'_i$ tilsvarer fire påfølgende biter i den binære strengen $s_i$. Mer spesifikt kan det for hvert siffer $s'_{i,j}$ bevises at det finnes en unik tuppel $(a, b, c, d)$ som tilfredsstiller $s'_{i,j} = 8a + 4b + 2c + d$ og $a, b, c, d \in \{0, 1\}$. Bitene i den binære strengen $s_i$ tilfredsstiller $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.

Utdata

Skriv ut et heltall — antallet gyldige følger $(p_2, p_3, \dots, p_n)$ modulo $998244353$.

Eksempel

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.