Universal Cup Judging System

Universal Cup

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

มีสตริงฐานสอง $s_1$ ความยาว $m$ เก็บอยู่บนดิสก์หมายเลข #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$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยสตริงเลขฐานสิบหก $s'_i$ ความยาว $m/4$ อักขระแต่ละตัวของ $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.