เมื่อเบื่อกับการคำนวณคำตอบของโจทย์แปลก ๆ แล้วนำไปหารเอาเศษด้วย $998244353$ หรือ $10^9+7$ 小 E จึงออกแบบปริศนาที่เกี่ยวกับ $2$:

กำหนดตารางที่มี $2$ แถวและ $2^k$ คอลัมน์ คุณต้องเติมจำนวน $1\sim2^{k+1}$ ลงในช่องทั้ง $2^{k+1}$ ช่องให้ครบโดยไม่ซ้ำ และทำให้ความสัมพันธ์มากน้อยระหว่างช่องที่ติดกันเป็นไปตามข้อจำกัดต่อไปนี้

กล่าวอย่างเจาะจง กำหนดลำดับศูนย์และหนึ่งสามลำดับ $a,b,c$ ที่มีความยาว $2^k-1,2^k,2^k-1$ ตามลำดับ เมทริกซ์ $A$ ขนาด $2\times2^k$ เป็นคำตอบของปริศนาก็ต่อเมื่อเป็นไปตามเงื่อนไขทั้งสี่ข้อพร้อมกัน:

1. $A$ มีจำนวนเต็มทุกจำนวนใน $1,2,\ldots,2^{k+1}$ อย่างละหนึ่งครั้งพอดี

2. สำหรับทุก $1\le i<2^k$ มี $a_i=[A_{1,i}<A_{1,i+1}]$

3. สำหรับทุก $1\le i\le2^k$ มี $b_i=[A_{1,i}<A_{2,i}]$

4. สำหรับทุก $1\le i<2^k$ มี $c_i=[A_{2,i}<A_{2,i+1}]$

โดย $[P]$ มีค่า $1$ เมื่อเงื่อนไข $P$ เป็นจริง และมีค่า $0$ ในกรณีอื่น

สำหรับคุณ การหาคำตอบใดคำตอบหนึ่งหรือตัดสินว่าไม่มีคำตอบนั้นง่ายเกินไป เนื่องจากเป็นปริศนาเกี่ยวกับ $2$ 小 E จึงขอให้คุณคำนวณจำนวนคำตอบของปริศนาแล้วหารเอาเศษด้วย $2$

小 E เตรียมปริศนา $t$ ข้อที่มีตารางขนาดเดียวกัน และบีบอัดรวมกันอย่างมีประสิทธิภาพ คุณต้องหาจำนวนคำตอบหารเอาเศษด้วย $2$ สำหรับปริศนาแต่ละข้อ

รายละเอียดการเขียนโปรแกรม

ผู้เข้าแข่งขันไม่จำเป็นต้องเขียน และไม่ควรเขียนฟังก์ชัน main

โปรแกรมที่ส่งต้องรวมไฟล์ส่วนหัว puzzle.h โดยเพิ่มโค้ดต่อไปนี้ที่ต้นโปรแกรม:

#include "puzzle.h"

คุณต้องเขียนฟังก์ชันต่อไปนี้ในไฟล์ซอร์สของโปรแกรมที่ส่ง:

unsigned puzzle(int t, int k, std::vector<unsigned> a,
    std::vector<unsigned> b, std::vector<unsigned> c);

• $t,k$ แทนจำนวนปริศนาและขนาดตารางตามลำดับ

• สำหรับ $0\le i<2^k-1$ บิตที่ $j$ ($0\le j<t$) ของ $a_i$ ในฐานสอง แทนข้อจำกัดความสัมพันธ์มากน้อยระหว่าง $A_{1,i+1}$ และ $A_{1,i+2}$ ในปริศนาข้อที่ $j+1$

• สำหรับ $0\le i<2^k$ บิตที่ $j$ ($0\le j<t$) ของ $b_i$ ในฐานสอง แทนข้อจำกัดความสัมพันธ์มากน้อยระหว่าง $A_{1,i+1}$ และ $A_{2,i+1}$ ในปริศนาข้อที่ $j+1$

• สำหรับ $0\le i<2^k-1$ บิตที่ $j$ ($0\le j<t$) ของ $c_i$ ในฐานสอง แทนข้อจำกัดความสัมพันธ์มากน้อยระหว่าง $A_{2,i+1}$ และ $A_{2,i+2}$ ในปริศนาข้อที่ $j+1$

• ฟังก์ชันต้องคืนจำนวนเต็มไม่ติดลบ โดยบิตที่ $j$ ($0\le j<t$) ในฐานสอง แทนจำนวนคำตอบของปริศนาข้อที่ $j+1$ หารเอาเศษด้วย $2$

• ในแต่ละชุดทดสอบ ไลบรารีจะเรียกฟังก์ชันนี้หนึ่งครั้งพอดี

หมายเหตุ: ในทุกกรณี ไลบรารีใช้เวลาไม่เกิน 0.1 วินาที และใช้หน่วยความจำขนาดคงที่ไม่เกิน 64 MiB

วิธีทดสอบโปรแกรม

ไฟล์ grader.cpp ในไดเรกทอรีโจทย์เป็นไลบรารีอ้างอิง ไลบรารีที่ใช้ในการทดสอบจริงมีการเขียนแตกต่างจากไลบรารีอ้างอิงนี้ ดังนั้นวิธีแก้ของคุณไม่ควรอาศัยรายละเอียดการเขียนไลบรารี

คุณสามารถใช้คำสั่งต่อไปนี้ในไดเรกทอรีโจทย์เพื่อคอมไพล์เป็นโปรแกรมที่รันได้:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

สำหรับโปรแกรมที่คอมไพล์ได้:

โปรแกรมจะอ่านข้อมูลจากข้อมูลนำเข้ามาตรฐานในรูปแบบต่อไปนี้:

• บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน $t,k$ แทนจำนวนปริศนาและขนาดตารางตามลำดับ

• บรรทัดที่ $3i-1$ ($1\le i\le t$) มีสตริงศูนย์และหนึ่ง $a_1\ldots a_{2^k-1}$ ความยาว $2^k-1$

• บรรทัดที่ $3i$ ($1\le i\le t$) มีสตริงศูนย์และหนึ่ง $b_1\ldots b_{2^k}$ ความยาว $2^k$

• บรรทัดที่ $3i+1$ ($1\le i\le t$) มีสตริงศูนย์และหนึ่ง $c_1\ldots c_{2^k-1}$ ความยาว $2^k-1$

โปรแกรมจะเขียนข้อมูลไปยังข้อมูลส่งออกมาตรฐานในรูปแบบต่อไปนี้:

• ผลลัพธ์มีทั้งหมด $t$ บรรทัด บรรทัดที่ $i$ ($1\le i\le t$) มีจำนวนเต็มไม่ติดลบ แทนจำนวนคำตอบของปริศนาข้อที่ $i$ หารเอาเศษด้วย $2$

ตัวอย่าง

ข้อมูลนำเข้า 1

2 1
1
01
1
1
00
1

ข้อมูลส่งออก 1

1
0

ข้อมูลนำเข้า 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

ข้อมูลส่งออก 2

1
1
0
0

คำอธิบายไฟล์แนบ

ในไฟล์แนบ:

1. grader.cpp เป็นไลบรารีอ้างอิงที่จัดให้

2. puzzle.h เป็นไฟล์ส่วนหัว คุณไม่จำเป็นต้องสนใจเนื้อหาภายใน

3. template_puzzle.cpp เป็นโค้ดตัวอย่างที่จัดให้ คุณสามารถใช้เป็นแนวทางในการเขียนโค้ดของตนเอง

งานย่อย

สำหรับข้อมูลทดสอบทั้งหมด:

• $1\le t\le32$, $1\le k\le18$

• สำหรับทุก $1\le i<2^k$ มี $a_i\in\{0,1\}$

• สำหรับทุก $1\le i\le2^k$ มี $b_i\in\{0,1\}$

• สำหรับทุก $1\le i<2^k$ มี $c_i\in\{0,1\}$

คุณสมบัติพิเศษ A: $t\le4$

คุณสมบัติพิเศษ B: สำหรับทุก $1\le i<2^k$ มี $b_i\ne b_{i+1}$

วิธีให้คะแนน

หมายเหตุ:

• ผู้เข้าแข่งขันไม่ควรเข้าถึงข้อมูลภายในไลบรารีด้วยวิธีที่ไม่ได้รับอนุญาต เช่น โต้ตอบกับสตรีมข้อมูลนำเข้าหรือข้อมูลส่งออกมาตรฐานโดยตรง การกระทำดังกล่าวถือเป็นการทุจริต

• ไลบรารีที่ใช้ตัดสินจริงมีการเขียนแตกต่างจากไลบรารีตัวอย่าง

โจทย์นี้อยู่ภายใต้ข้อจำกัดเช่นเดียวกับโจทย์ทั่วไป เช่น การคอมไพล์ผิดพลาดทำให้ได้ 0 คะแนนทั้งข้อ ส่วนข้อผิดพลาดขณะทำงาน การใช้เวลาเกินกำหนด หรือใช้หน่วยความจำเกินกำหนด จะทำให้ได้ 0 คะแนนในชุดทดสอบที่เกี่ยวข้อง คุณเข้าถึงได้เฉพาะตัวแปรที่นิยามเองและตัวแปรที่ไลบรารีจัดให้ การพยายามเข้าถึงพื้นที่แอดเดรสอื่นอาจทำให้คอมไพล์ผิดพลาดหรือเกิดข้อผิดพลาดขณะทำงาน

ภายใต้เงื่อนไขข้างต้น:

• ในแต่ละชุดทดสอบ โปรแกรมจะได้คะแนนเต็มก็ต่อเมื่อคำตอบที่คืนจากการเรียกฟังก์ชัน puzzle ถูกต้อง