Fatigué de calculer les réponses à des problèmes étranges modulo $998244353$ ou $10^9+7$, 小 E a conçu une énigme liée à $2$ :

Étant donnée une grille de $2$ lignes et $2^k$ colonnes, tu dois placer les entiers de $1$ à $2^{k+1}$ dans ses $2^{k+1}$ cases, chacun exactement une fois, en respectant les contraintes suivantes sur les comparaisons entre cases voisines.

Plus précisément, on donne trois suites binaires $a,b,c$, de longueurs respectives $2^k-1,2^k,2^k-1$. Une matrice $A$ de taille $2\times2^k$ est une solution de l'énigme si et seulement si elle satisfait simultanément les quatre conditions suivantes :

1. $A$ contient chacun des entiers $1,2,\ldots,2^{k+1}$ exactement une fois.
2. Pour tout $1\le i<2^k$, $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Pour tout $1\le i\le2^k$, $b_i=[A_{1,i}<A_{2,i}]$.
4. Pour tout $1\le i<2^k$, $c_i=[A_{2,i}<A_{2,i+1}]$.

Ici, $[P]$ vaut $1$ si la condition $P$ est vraie, et $0$ sinon.

Trouver une solution quelconque ou déterminer qu'il n'en existe aucune serait trop simple pour toi. Puisque cette énigme concerne $2$, 小 E te demande de calculer le nombre de solutions modulo $2$.

小 E a préparé $t$ énigmes dont les grilles ont toutes la même taille, et les a regroupées au moyen d'une compression efficace. Pour chacune, tu dois calculer le nombre de solutions modulo $2$.

Détails d'implémentation

Tu n'as pas à implémenter la fonction main, et tu ne dois pas le faire.

Le programme soumis doit inclure le fichier d'en-tête puzzle.h. Ajoute donc au début du programme :

#include "puzzle.h"

Tu dois implémenter la fonction suivante dans le fichier source soumis :

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

• $t,k$ représentent respectivement le nombre d'énigmes et la taille de la grille.
• Pour $0\le i<2^k-1$, le bit $j$ de $a_i$ en binaire, où $0\le j<t$, représente la contrainte de comparaison entre $A_{1,i+1}$ et $A_{1,i+2}$ dans l'énigme $j+1$.
• Pour $0\le i<2^k$, le bit $j$ de $b_i$ en binaire, où $0\le j<t$, représente la contrainte de comparaison entre $A_{1,i+1}$ et $A_{2,i+1}$ dans l'énigme $j+1$.
• Pour $0\le i<2^k-1$, le bit $j$ de $c_i$ en binaire, où $0\le j<t$, représente la contrainte de comparaison entre $A_{2,i+1}$ et $A_{2,i+2}$ dans l'énigme $j+1$.
• La fonction doit renvoyer un entier non négatif dont le bit $j$ en binaire, pour $0\le j<t$, représente le nombre de solutions de l'énigme $j+1$ modulo $2$.
• Pour chaque test, la bibliothèque d'interaction appelle cette fonction exactement une fois.

Remarque : dans tous les cas, le temps d'exécution de la bibliothèque d'interaction ne dépasse pas $0.1$ seconde. Sa consommation de mémoire est fixe et ne dépasse pas $64$ MiB.

Tester le programme

Le fichier grader.cpp du répertoire du problème est une implémentation de référence de la bibliothèque d'interaction. L'implémentation utilisée pour les tests finaux est différente ; ta solution ne doit donc pas dépendre des détails de cette implémentation.

Tu peux compiler un exécutable dans le répertoire du problème avec la commande :

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

Pour l'exécutable obtenu :

• Il lit sur l'entrée standard des données au format suivant :

  • La première ligne contient deux entiers positifs $t,k$, le nombre d'énigmes et la taille de la grille.
  • La ligne $3i-1$, pour $1\le i\le t$, contient une chaîne binaire $a_1\ldots a_{2^k-1}$ de longueur $2^k-1$.
  • La ligne $3i$, pour $1\le i\le t$, contient une chaîne binaire $b_1\ldots b_{2^k}$ de longueur $2^k$.
  • La ligne $3i+1$, pour $1\le i\le t$, contient une chaîne binaire $c_1\ldots c_{2^k-1}$ de longueur $2^k-1$.

• Il écrit sur la sortie standard des données au format suivant :

  • La sortie comporte $t$ lignes. La ligne $i$, pour $1\le i\le t$, contient un entier non négatif représentant le nombre de solutions de l'énigme $i$ modulo $2$.

Exemples

Entrée 1

2 1
1
01
1
1
00
1

Sortie 1

1
0

Entrée 2

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

Sortie 2

1
1
0
0

Fichiers joints

Dans les fichiers joints :

1. grader.cpp est l'implémentation de référence fournie de la bibliothèque d'interaction.
2. puzzle.h est le fichier d'en-tête ; tu n'as pas à te préoccuper de son contenu.
3. template_puzzle.cpp est le code d'exemple fourni, dont tu peux t'inspirer pour écrire ton propre code.

Sous-tâches

Pour toutes les données de test :

• $1\le t\le32$, $1\le k\le18$ ;
• Pour tout $1\le i<2^k$, $a_i\in\{0,1\}$ ;
• Pour tout $1\le i\le2^k$, $b_i\in\{0,1\}$ ;
• Pour tout $1\le i<2^k$, $c_i\in\{0,1\}$.

Propriété particulière A : $t\le4$.

Propriété particulière B : pour tout $1\le i<2^k$, $b_i\ne b_{i+1}$.

Sous-tâches

Remarque :

• Tu ne dois pas obtenir d'informations internes de la bibliothèque d'interaction par des moyens interdits, par exemple en communiquant directement avec les flux d'entrée et de sortie standard. Un tel comportement sera considéré comme de la triche.
• L'implémentation de la bibliothèque d'évaluation finale est différente de celle de la bibliothèque d'exemple.

Cette épreuve est d'abord soumise aux mêmes restrictions qu'un problème classique : une erreur de compilation donne $0$ point pour l'ensemble du problème ; une erreur d'exécution, un dépassement de temps ou de mémoire donne $0$ point au test concerné. Tu ne peux accéder dans le programme qu'aux variables que tu as définies et à celles fournies par la bibliothèque d'interaction. Tenter d'accéder à d'autres espaces d'adressage peut provoquer une erreur de compilation ou d'exécution.

Sous ces conditions :

• Pour chaque test, le programme obtient tous les points si et seulement si la réponse renvoyée lors de l'appel à puzzle est correcte.