P15362 [CTS 2026] Puzzle II (No testdata yet).

Tired of computing the answers to various strange problems modulo $998244353$ or $10^9 + 7$, Little E designed a puzzle related to $2$: Given a grid with $2$ rows and $2^k$ columns, you need to fill the $2^{k+1}$ cells with all integers from $1$ to $2^{k+1}$, with no repeats and nothing missing, and make the size relations between adjacent cells satisfy the restrictions below. More specifically, you are given three $01$ sequences $a, b, c$ of lengths $2^k - 1$, $2^k$, and $2^k - 1$, respectively. A $2 \times 2^k$ matrix $A$ is called a solution to this puzzle if and only if it satisfies all four constraints: 1. $A$ contains each integer in $1, 2, \dots, 2^{k+1}$ **exactly once**. 2. For all $1 \le i < 2^k$, $a_i = [A_{1,i} < A_{1,i+1}]$. 3. For all $1 \le i \le 2^k$, $b_i = [A_{1,i} < A_{2,i}]$. 4. For all $1 \le i < 2^k$, $c_i = [A_{2,i} < A_{2,i+1}]$. Here, $[P]$ equals $1$ when condition $P$ holds, and $0$ otherwise. For you, finding any solution or just determining that no solution exists is too easy. Since this is a puzzle about $2$, Little E asks you to compute the number of solutions modulo $2$. Little E prepared $t$ puzzles with the same grid size, and compressed them together using an efficient compression method. You need to compute, for each puzzle, the number of solutions modulo $2$. ### Implementation Details Contestants do not need to, and should not, implement the `main` function. You need to make sure your submitted program includes the header file `puzzle.h`, i.e. add the following code at the beginning: ```cpp #include "puzzle.h" ``` You need to implement the following function in your submitted source file: ```cpp unsigned puzzle(int t, int k, std::vector a, std::vector b, std::vector c); ``` - $t$ and $k$ denote the number of puzzles and the grid size, respectively. - For $0 \le i < 2^k - 1$, the **$j$-th bit ($0 \le j < t$) in binary** of $a_i$ represents, in the $(j+1)$-th puzzle, the constraint on the size relation between $A_{1,i+1}$ and $A_{1,i+2}$. - For $0 \le i < 2^k$, the **$j$-th bit ($0 \le j < t$) in binary** of $b_i$ represents, in the $(j+1)$-th puzzle, the constraint on the size relation between $A_{1,i+1}$ and $A_{2,i+1}$. - For $0 \le i < 2^k - 1$, the **$j$-th bit ($0 \le j < t$) in binary** of $c_i$ represents, in the $(j+1)$-th puzzle, the constraint on the size relation between $A_{2,i+1}$ and $A_{2,i+2}$. - This function should return a non-negative integer, where the **$j$-th bit ($0 \le j < t$) in binary** represents, for the $(j+1)$-th puzzle, the number of solutions modulo $2$. - For each test point, this function will be called by the interaction library exactly once. Note: In all cases, the time needed by the interaction library will not exceed $0.1$ seconds. The memory usage is fixed-size and will not exceed $64$ MiB. ### Test Program Usage In the problem directory, `grader.cpp` is the reference implementation of the interaction library. The interaction library used in the final test is different from this reference implementation, so your solution should not rely on the interaction library implementation. You can compile an executable in this problem directory using the following command: ```bash g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static ```

For the compiled executable program: - The executable will read input from standard input in the following format: - The first line contains two positive integers $t, k$, representing the number of puzzles and the grid size, respectively. - Line $3i-1$ ($1 \le i \le t$) contains a $01$ string of length $2^k - 1$, $a_1 \dots a_{2^k - 1}$. - Line $3i$ ($1 \le i \le t$) contains a $01$ string of length $2^k$, $b_1 \dots b_{2^k}$. - Line $3i+1$ ($1 \le i \le t$) contains a $01$ string of length $2^k - 1$, $c_1 \dots c_{2^k - 1}$.

- The executable will output to standard output in the following format: - There are a total of $t$ lines. Line $i$ ($1 \le i \le t$) contains a non-negative integer, representing, for the $i$-th puzzle, the number of solutions modulo $2$.

### Additional File Notes In the additional files: 1. `grader.cpp` is the provided reference implementation of the interaction library. 2. `puzzle.h` is the header file. Contestants do not need to care about its content. 3. `template_puzzle.cpp` is the provided sample code. You may refer to it and implement your own code. ### Subtasks For all testdata, it holds that: - $1 \le t \le 32$, $1 \le k \le 18$. - For all $1 \le i < 2^k$, $a_i \in \{0,1\}$. - For all $1 \le i \le 2^k$, $b_i \in \{0,1\}$. - For all $1 \le i < 2^k$, $c_i \in \{0,1\}$. ::cute-table{tuack} | Subtask ID | Score | $k \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1$ | $5$ | $2$ | None | | $2$ | ^ | $3$ | ^ | | $3$ | ^ | $6$ | ^ | | $4$ | ^ | $8$ | ^ | | $5$ | ^ | $10$ | ^ | | $6$ | $25$ | $13$ | A | | $7$ | $5$ | $14$ | None | | $8$ | $20$ | $17$ | A | | $9$ | $10$ | $18$ | B | | $10$ | $15$ | ^ | None | Special Property A: $t \le 4$. Special Property B: For all $1 \le i < 2^k$, $b_i \ne b_{i+1}$. ### Scoring **Note:** - Contestants should not obtain internal information from the interaction library through illegal means, such as interacting directly with standard input and output streams. Such behavior will be considered cheating. - The final judging interaction library is implemented differently from the sample interaction library. - This problem is first subject to the same limits as traditional problems. For example, compilation errors will make the whole problem score $0$. Runtime errors, exceeding the time limit, exceeding the memory limit, etc. will make the corresponding test point score $0$. Contestants may only access variables they define and variables provided by the interaction library. Attempting to access other address spaces may cause compilation errors or runtime errors. Based on the above conditions: - For each test point, the program gets full score if and only if the returned answer is correct when the `puzzle` function is called. Translated by ChatGPT 5