Universal Cup Judging System

Universal Cup

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

喺 $1$ 號磁碟上面儲存咗一個長度係 $m$ 嘅二進制字串 $s_1$。

跟住有 $n - 1$ 次操作。喺第 $i$ 次操作入面,會揀一個編號滿足 $1 \le p_{i+1} \le i$ 嘅磁碟,然後將嗰個磁碟上面嘅字串 $s_{p_{i+1}}$ 複製到磁碟 $i + 1$,產生 $s_{i+1}$。不過,喺複製過程入面,最多可能會有 $k$ 個位元被翻轉(即係最多喺 $k$ 個位置發生錯誤)。

宜家畀你最後全部 $n$ 個二進制字串 $s_1, s_2, \dots, s_n$,每個字串嘅長度都係 $m$。你嘅任務係計算有幾多個可能嘅序列 $p_2, p_3, \dots, p_n$ 可以產生呢個最終配置。

由於答案可能好大,你只需要求答案對 $998244353$ 取模嘅結果。

輸入格式

輸入嘅第一行包含三個整數 $n, m, k$($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$),含義如題目所述。保證 $m$ 係 $4$ 嘅倍數。

接落嚟嘅 $n$ 行,每行包含一個長度係 $m/4$ 嘅十六進制字串 $s'_i$。$s'_i$ 嘅每個字元都係 0–9 或者 A–F 之一,其中 $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$。

十六進制表示 $s'_i$ 入面嘅每一位對應二進制字串 $s_i$ 入面嘅連續四個位元。具體嚟講,對於每一位 $s'_{i,j}$,可以證明存在唯一嘅四元組 $(a, b, c, d)$ 滿足 $s'_{i,j} = 8a + 4b + 2c + d$ 同埋 $a, b, c, d \in \{0, 1\}$。二進制字串 $s_i$ 入面嘅位元滿足 $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$。

輸出格式

輸出一個整數 — 合法序列 $(p_2, p_3, \dots, p_n)$ 嘅數量對 $998244353$ 取模嘅結果。

範例

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.