اهتمت 露露 و花花 و萱萱 مؤخرًا بالأعداد العشوائية في الحاسوب. ومن المعروف أن تسلسل الأعداد العشوائية الذي يولده الحاسوب ليس عشوائيًا حقًا، بل هو تسلسل شبه عشوائي يُنتَج وفق قواعد محددة.
في أحد الأيام، تعرّفت 露露 على طريقة لتوليد الأعداد العشوائية تُسمى Mersenne twister. عند إعطاء المعاملين الابتدائيين $m\in\mathbb Z^+$ و$x\in\mathbb Z\cap[0,2^m)$، والقيمة الابتدائية $M_0\in\mathbb Z\cap[0,2^m)$، فإنها تبني التسلسل شبه العشوائي $\{M_n\}$ باستخدام العلاقة التكرارية التالية:
$$M_n=\begin{cases} 2M_{n-1},&2M_{n-1}<2^m,\\ (2M_{n-1}-2^m)\operatorname{xor}x,&2M_{n-1}\ge2^m. \end{cases}$$
تمثل xor عملية «أو الحصرية» على البتات، أي العملية ^ في C/C++. إذا كان اختيار المعامل $x$ يجعل قيم التسلسل موزعة بالتساوي تقريبًا على $\mathbb Z\cap(0,2^m)$ عندما يؤول طوله إلى ما لا نهاية، فإننا نسمي $x$ «جيدًا». على سبيل المثال، عندما $m>1$، فمن الواضح أن $x=0$ ليس جيدًا.
بعد أن شرحت 露露 طريقة Mersenne twister لأصدقائها، أرادت 花花 استخدام بعض اختبارات العشوائية التقليدية لفحص قوة عشوائيتها، ولذلك حسبت بعض قيم $M_k$ باستخدام الحاسوب.
لكن 萱萱 اليقظة لاحظت أن 花花 أضافت بالخطأ $l$ أصفار إلى نهاية التمثيل الثنائي للعدد $k$ عند إدخاله في إحدى المرات. وبينما كانت تستعد لتنبيهها، كانت 花花 قد حسبت القيمة الخاطئة لـ$M_k$ وسجلتها، من دون تسجيل قيمة $k$. ورغم أن هذا الخطأ ليس كارثيًا، فإن 花花 المحبة للكمال، عندما أخبرتها 萱萱 بالسهو، توسلت إليها أن تساعدها على تصحيح قيمة $M_k$. وهكذا أوكلت 萱萱 المهمة إلى ذكائها الاصطناعي: أنت.
الإدخال
يحتوي السطر الأول من ملف الإدخال random.in على عدد صحيح موجب $m$. يحتوي السطر الثاني على التمثيل الثنائي للعدد $x$، ويتكون من $m$ أعداد مرتبة من البت الأقل أهمية إلى البت الأعلى أهمية. يحتوي السطر الثالث على التمثيل الثنائي لـ$M_0$ بالترتيب نفسه، ويحتوي السطر الرابع على عدد صحيح $type$.
بعد ذلك توجد حالتان محتملتان:
- إذا كان $type=0$، أي إن 萱萱 سجلت ما أدخلته 花花، فإن السطر الخامس يحتوي على عدد صحيح يمثل قيمة $k$ الصحيحة التي سجلتها 萱萱.
- إذا كان $type=1$، أي إن 萱萱 لم تتمكن من تسجيل ما أدخلته 花花، فإن السطر الخامس يحتوي على $l$، ويحتوي السطر السادس على التمثيل الثنائي للقيمة الخاطئة لـ$M_k$ التي حسبتها 花花.
الإخراج
يتكون ملف الإخراج random.out من سطر واحد فقط، يحوي سلسلة من $m$ بتات، كل منها 0 أو 1، تمثل قيمة $M_k$ الصحيحة التي حسبتها. يجب أيضًا ترتيب البتات من الأقل أهمية إلى الأعلى أهمية.
أمثلة
الإدخال 1
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
الإخراج 1
0101111001
الإدخال 2
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 3 0 1 0 1 1 1 1 1 0 1
الإخراج 2
0101111001
المثال 3
انظر الملفين random/random.in وrandom/random.ans في دليل المتسابق.
القيود
| رقم الاختبار | $m$ | $k$ | $l$ | $type$ | هل $x$ جيد؟ |
|---|---|---|---|---|---|
| 1 | $\le10$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 2 | $\le10$ | $\le10^9$ | $\le10$ | 1 | نعم |
| 3 | $\le100$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 4 | $\le100$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 5 | $\le100$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 6 | $\le100$ | $\le10^5$ | $=1$ | 1 | نعم |
| 7 | $\le100$ | $\le10^9$ | $\le10$ | 1 | نعم |
| 8 | $\le100$ | $\le10^9$ | $\le10$ | 1 | نعم |
| 9 | $\le100$ | $\le10^9$ | $\le10$ | 1 | نعم |
| 10 | $\le1000$ | $\le10^18$ | $\le10$ | 1 | نعم |
| 11 | $\le1000$ | $\le10^18$ | $\le10$ | 1 | نعم |
| 12 | $\le1000$ | $\le10^18$ | $\le10$ | 1 | نعم |
| 13 | $\le2000$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 14 | $\le2000$ | $\le10^9$ | لا ينطبق | 0 | نعم |
| 15 | $\le500000$ | $\le10^6$ | لا ينطبق | 0 | لا |
| 16 | $\le500000$ | $\le10^6$ | لا ينطبق | 0 | لا |
| 17 | $\le1000000$ | $\le10^6$ | لا ينطبق | 0 | لا |
| 18 | $\le1000000$ | $\le10^6$ | لا ينطبق | 0 | لا |
| 19 | $\le1000000$ | $\le10^6$ | لا ينطبق | 0 | لا |
| 20 | $\le1000000$ | $\le10^6$ | لا ينطبق | 0 | لا |