Chán việc tính đáp án của những bài toán kỳ lạ theo modulo $998244353$ hoặc $10^9+7$, 小 E đã thiết kế một câu đố liên quan đến $2$:

Cho một lưới gồm $2$ hàng và $2^k$ cột. Bạn cần điền các số từ $1$ đến $2^{k+1}$ vào $2^{k+1}$ ô của lưới, không lặp và không thiếu, sao cho quan hệ lớn nhỏ giữa các ô kề nhau thỏa mãn những ràng buộc sau.

Cụ thể, cho ba dãy nhị phân $a,b,c$ có độ dài lần lượt là $2^k-1,2^k,2^k-1$. Một ma trận $A$ kích thước $2\times2^k$ được gọi là một lời giải của câu đố khi và chỉ khi đồng thời thỏa mãn bốn điều kiện:

1. $A$ chứa mỗi số nguyên trong $1,2,\ldots,2^{k+1}$ đúng một lần;
2. Với mọi $1\le i<2^k$, có $a_i=[A_{1,i}<A_{1,i+1}]$;
3. Với mọi $1\le i\le2^k$, có $b_i=[A_{1,i}<A_{2,i}]$;
4. Với mọi $1\le i<2^k$, có $c_i=[A_{2,i}<A_{2,i+1}]$.

Ở đây, $[P]$ bằng $1$ khi điều kiện $P$ đúng và bằng $0$ nếu ngược lại.

Đối với bạn, chỉ tìm một lời giải bất kỳ hoặc xác định vô nghiệm là quá đơn giản. Vì đây là câu đố về $2$, 小 E yêu cầu bạn tính số lượng lời giải modulo $2$.

小 E đã chuẩn bị $t$ câu đố có cùng kích thước lưới và dùng phương pháp nén hiệu quả để gộp chúng lại. Bạn cần tìm số lượng lời giải modulo $2$ cho từng câu đố.

Chi tiết cài đặt

Thí sinh không cần và cũng không nên cài đặt hàm main.

Chương trình nộp phải bao gồm tệp tiêu đề puzzle.h, bằng cách thêm đoạn mã sau ở đầu chương trình:

#include "puzzle.h"

Bạn cần cài đặt hàm sau trong tệp mã nguồn nộp:

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

• $t,k$ lần lượt biểu thị số câu đố và kích thước lưới.
• Với $0\le i<2^k-1$, bit thứ $j$ ($0\le j<t$) trong biểu diễn nhị phân của $a_i$ biểu thị ràng buộc quan hệ lớn nhỏ giữa $A_{1,i+1}$ và $A_{1,i+2}$ trong câu đố thứ $j+1$.
• Với $0\le i<2^k$, bit thứ $j$ ($0\le j<t$) trong biểu diễn nhị phân của $b_i$ biểu thị ràng buộc quan hệ lớn nhỏ giữa $A_{1,i+1}$ và $A_{2,i+1}$ trong câu đố thứ $j+1$.
• Với $0\le i<2^k-1$, bit thứ $j$ ($0\le j<t$) trong biểu diễn nhị phân của $c_i$ biểu thị ràng buộc quan hệ lớn nhỏ giữa $A_{2,i+1}$ và $A_{2,i+2}$ trong câu đố thứ $j+1$.
• Hàm cần trả về một số nguyên không âm; bit thứ $j$ ($0\le j<t$) trong biểu diễn nhị phân của nó là số lượng lời giải modulo $2$ của câu đố thứ $j+1$.
• Trong mỗi bộ kiểm tra, thư viện chấm gọi hàm này đúng một lần.

Lưu ý: trong mọi trường hợp, thời gian chạy của thư viện chấm không vượt quá 0.1 giây; bộ nhớ sử dụng có kích thước cố định và không vượt quá 64 MiB.

Cách kiểm tra chương trình

grader.cpp trong thư mục bài là bản cài đặt tham khảo của thư viện chấm. Bản dùng để chấm chính thức khác với bản tham khảo này, vì vậy lời giải không được phụ thuộc vào cách cài đặt thư viện chấm.

Bạn có thể dùng lệnh sau trong thư mục bài để biên dịch thành chương trình thực thi:

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

Đối với chương trình thực thi đã biên dịch:

• Chương trình đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

  • Dòng đầu tiên chứa hai số nguyên dương $t,k$, lần lượt là số câu đố và kích thước lưới.
  • Dòng thứ $3i-1$ ($1\le i\le t$) chứa chuỗi nhị phân $a_1\ldots a_{2^k-1}$ có độ dài $2^k-1$.
  • Dòng thứ $3i$ ($1\le i\le t$) chứa chuỗi nhị phân $b_1\ldots b_{2^k}$ có độ dài $2^k$.
  • Dòng thứ $3i+1$ ($1\le i\le t$) chứa chuỗi nhị phân $c_1\ldots c_{2^k-1}$ có độ dài $2^k-1$.

• Chương trình ghi dữ liệu ra đầu ra chuẩn theo định dạng sau:

  • Có $t$ dòng; dòng thứ $i$ ($1\le i\le t$) chứa một số nguyên không âm là số lượng lời giải modulo $2$ của câu đố thứ $i$.

Ví dụ

Dữ liệu vào 1

2 1
1
01
1
1
00
1

Dữ liệu ra 1

1
0

Dữ liệu vào 2

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

Dữ liệu ra 2

1
1
0
0

Mô tả tệp đính kèm

Trong các tệp đính kèm:

1. grader.cpp là bản cài đặt tham khảo của thư viện chấm.
2. puzzle.h là tệp tiêu đề, thí sinh không cần quan tâm đến nội dung cụ thể.
3. template_puzzle.cpp là mã ví dụ được cung cấp; thí sinh có thể tham khảo để cài đặt mã của mình.

Nhiệm vụ con

Với mọi dữ liệu kiểm tra:

• $1\le t\le32$, $1\le k\le18$;
• Với mọi $1\le i<2^k$, có $a_i\in\{0,1\}$;
• Với mọi $1\le i\le2^k$, có $b_i\in\{0,1\}$;
• Với mọi $1\le i<2^k$, có $c_i\in\{0,1\}$.

Tính chất đặc biệt A: $t\le4$.

Tính chất đặc biệt B: với mọi $1\le i<2^k$, có $b_i\ne b_{i+1}$.

Nhiệm vụ con

Lưu ý:

• Thí sinh không được lấy thông tin nội bộ của thư viện chấm bằng cách trái phép, chẳng hạn tương tác trực tiếp với luồng đầu vào và đầu ra chuẩn. Hành vi này bị coi là gian lận.
• Cách cài đặt thư viện chấm chính thức khác với thư viện chấm mẫu.

Trước hết, bài này chịu các giới hạn như bài truyền thống: chẳng hạn lỗi biên dịch khiến cả bài được $0$ điểm; lỗi khi chạy, vượt giới hạn thời gian hoặc bộ nhớ khiến bộ kiểm tra tương ứng được $0$ điểm. Thí sinh chỉ được truy cập các biến do mình định nghĩa và các biến do thư viện chấm cung cấp; cố truy cập không gian địa chỉ khác có thể dẫn đến lỗi biên dịch hoặc lỗi khi chạy.

Dựa trên những điều kiện trên:

• Với mỗi bộ kiểm tra, chương trình được điểm tối đa khi và chỉ khi đáp án trả về khi gọi hàm puzzle là đúng.