Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100
İstatistikler

Terdapat sebuah string biner $s_1$ dengan panjang $m$ yang disimpan pada diska #1.

Kemudian, terdapat $n - 1$ operasi. Pada operasi ke-$i$, sebuah diska $1 \le p_{i+1} \le i$ dipilih, dan string $s_{p_{i+1}}$ pada diska tersebut disalin ke diska $i + 1$, menghasilkan $s_{i+1}$. Namun, selama proses penyalinan, hingga $k$ bit dapat terbalik (yaitu, kesalahan terjadi pada paling banyak $k$ posisi).

Anda diberikan seluruh $n$ string biner akhir $s_1, s_2, \dots, s_n$, masing-masing dengan panjang $m$. Tugas Anda adalah menentukan berapa banyak barisan $p_2, p_3, \dots, p_n$ yang mungkin yang dapat menghasilkan konfigurasi akhir ini.

Karena jawabannya bisa sangat besar, Anda hanya perlu mencari jawaban modulo $998244353$.

Masukan

Baris pertama masukan berisi tiga bilangan bulat $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), seperti yang dijelaskan pada deskripsi soal. Dijamin bahwa $m$ adalah kelipatan dari $4$.

Masing-masing dari $n$ baris berikutnya berisi sebuah string heksadesimal $s'_i$ dengan panjang $m/4$. Setiap karakter dari $s'_i$ adalah salah satu dari 0–9 atau A–F, dengan $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.

Setiap digit pada representasi heksadesimal $s'_i$ bersesuaian dengan empat bit berurutan pada string biner $s_i$. Secara spesifik, untuk setiap digit $s'_{i,j}$, dapat dibuktikan bahwa terdapat tupel unik $(a, b, c, d)$ yang memenuhi $s'_{i,j} = 8a + 4b + 2c + d$ dan $a, b, c, d \in \{0, 1\}$. Bit-bit pada string biner $s_i$ memenuhi $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.

Keluaran

Cetak sebuah bilangan bulat — banyaknya barisan valid $(p_2, p_3, \dots, p_n)$ modulo $998244353$.

Contoh

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.