Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 1024 MB Points totaux : 100
Statistiques

توجد سلسلة ثنائية $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.