No.2442 線形写像

問題文

入力に非負整数 $N$ と、 $2^{64}$ 未満の非負整数のみからなる長さ $2^N$ の数列 $A$ が与えられます。

まずは記法と用語を導入します。 $2^N$ 未満の非負整数 $i$ に対し、 $A$ の $1+i$ 個目の成分を $A_i$ と書き表します。

非負整数 $i, j$ に対し、 $i$ と $j$ のbit排他的論理和を $i \textrm{ XOR } j$ と書き表します：

bit排他的論理和を知らない人向けの説明はこちらです。（クリックで開く）

$i \textrm{ XOR } j$ は、次の条件を満たす一意な非負整数 $k$ です。

任意の非負整数 $d$ に対し、

$i$ と $j$ の二進法表記における $2^d$ の位が等しいならば、 $k$ の二進法表記における $2^d$ の位は $0$ である。
$i$ と $j$ の二進法表記における $2^d$ の位が等しくないならば、 $k$ の二進法表記における $2^d$ の位は $1$ である。

ただし各非負整数 $n$ と $d$ に対し、 $n$ の二進法表記における $2^d$ の位とは $n$ を $2^d$ で割った商を $2$ で割った余りを表します。

$A$ が良い数列であるとは、次の条件を満たすということです：

$2^N$ 未満の任意の非負整数 $i, j$ に対し、 $A_{i \textrm{ XOR } j} = A_i \textrm{ XOR } A_j$ である。

$A$ が良い数列であるか否かを判定してください。

背景

まず非負整数 $n$ に対し、 $2^n$ 未満の非負整数全体の集合は各要素の二進法表記を考えることで $2$ 元体 $\mathbb{F}_2$ 上の線形空間 $\mathbb{F}_2^n$ と同一視することができます。線形代数を知らない人向けに大雑把に説明をすると、 $\mathbb{F}_2^n$ は $0$ か $1$ （と同一視される項）のみからなる長さ $n$ の数列全体の集合です。

$A$ が良い数列であることは、上記の同一視のもとで $A$ が定める写像 $\mathbb{F}_2^N \to \mathbb{F}_2^{64}$ （ $\mathbb{F}_2^N$ の要素を代入して $\mathbb{F}_2^{64}$ の要素を返す関数）が線形写像であるということと同値です。従って本問は、与えられた写像 $\mathbb{F}_2^N \to \mathbb{F}_2^{64}$ が線形写像であるか否かを判定する問題と等価です。

入力

入力は以下の形式で標準入力から $1 + N$ 行で与えられます：

$1$ 行目に $N$ が与えられます。
$2^N$ 未満の各非負整数 $i$ に対し、 $2 + i$ 行目に $A_i$ が与えられます。

 $N$ 
 $A_0$ 
 $\vdots$ 
 $A_{2^N-1}$

制約

入力は以下の制約を満たします：

$N$ は $0 \leq N \leq 17$ を満たす整数である。
$2^N$ 未満の任意の非負整数 $i$ に対し、 $A_i$ は $0 \leq A_i < 2^{64}$ を満たす整数である。

出力

$A$ が良い数列である場合はYesと出力し、そうでない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1

入力

0
0

出力

Yes

$A = (0)$ です。 $2^N = 2^0 = 1$ 未満の非負整数は $0$ のみであり、

$\displaystyle \begin{array}{lclcl} \displaystyle A_{0 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 0 \\ \displaystyle A_0 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 0 &\displaystyle = & 0 \end{array}$

となるので $A$ は良い数列です。

サンプル2

入力

0
1

出力

No

$A = (1)$ です。

$\displaystyle \begin{array}{lclcl} \displaystyle A_{0 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 1 \\ \displaystyle A_0 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 1 &\displaystyle = & 0 \end{array}$

となるので $A$ は良い数列ではありません。

サンプル3

入力

1
2
1

出力

No

$A = (2,1)$ です。

$\displaystyle \begin{array}{lclcl} \displaystyle A_{0 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 2 \\ \displaystyle A_0 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 2 \textrm{ XOR } 2 &\displaystyle = & 0 \end{array}$

となるので $A$ は良い数列ではありません。

サンプル4

入力

出力

Yes

$A = (0,1,0,1)$ です。 $2^N = 2^2 = 4$ 未満の非負整数は $0,1,2,3$ の $4$ つのみであり、

$\displaystyle \begin{array}{lclcl} \displaystyle A_{0 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 0 \\ \displaystyle A_0 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 0 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{0 \textrm{ XOR } 1} &\displaystyle = &\displaystyle A_1 &\displaystyle = & 1 \\ \displaystyle A_0 \textrm{ XOR } A_1 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 1 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{0 \textrm{ XOR } 2} &\displaystyle = &\displaystyle A_2 &\displaystyle = & 0 \\ \displaystyle A_0 \textrm{ XOR } A_2 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 0 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{0 \textrm{ XOR } 3} &\displaystyle = &\displaystyle A_3 &\displaystyle = & 1 \\ \displaystyle A_0 \textrm{ XOR } A_3 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 1 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{1 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_1 &\displaystyle = & 1 \\ \displaystyle A_1 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 0 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{1 \textrm{ XOR } 1} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 0 \\ \displaystyle A_1 \textrm{ XOR } A_1 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 1 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{1 \textrm{ XOR } 2} &\displaystyle = &\displaystyle A_3 &\displaystyle = & 1 \\ \displaystyle A_1 \textrm{ XOR } A_2 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 0 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{1 \textrm{ XOR } 3} &\displaystyle = &\displaystyle A_2 &\displaystyle = & 0 \\ \displaystyle A_1 \textrm{ XOR } A_3 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 1 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{2 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_2 &\displaystyle = & 0 \\ \displaystyle A_2 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 0 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{2 \textrm{ XOR } 1} &\displaystyle = &\displaystyle A_3 &\displaystyle = & 1 \\ \displaystyle A_2 \textrm{ XOR } A_1 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 1 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{2 \textrm{ XOR } 2} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 0 \\ \displaystyle A_2 \textrm{ XOR } A_2 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 0 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{2 \textrm{ XOR } 3} &\displaystyle = &\displaystyle A_1 &\displaystyle = & 1 \\ \displaystyle A_2 \textrm{ XOR } A_3 &\displaystyle = &\displaystyle 0 \textrm{ XOR } 1 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{3 \textrm{ XOR } 0} &\displaystyle = &\displaystyle A_3 &\displaystyle = & 1 \\ \displaystyle A_3 \textrm{ XOR } A_0 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 0 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{3 \textrm{ XOR } 1} &\displaystyle = &\displaystyle A_2 &\displaystyle = & 0 \\ \displaystyle A_3 \textrm{ XOR } A_1 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 1 &\displaystyle = & 0 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{3 \textrm{ XOR } 2} &\displaystyle = &\displaystyle A_1 &\displaystyle = & 1 \\ \displaystyle A_3 \textrm{ XOR } A_2 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 0 &\displaystyle = & 1 \\ \displaystyle &\displaystyle &\displaystyle \\ \displaystyle A_{3 \textrm{ XOR } 3} &\displaystyle = &\displaystyle A_0 &\displaystyle = & 0 \\ \displaystyle A_3 \textrm{ XOR } A_3 &\displaystyle = &\displaystyle 1 \textrm{ XOR } 1 &\displaystyle = & 0 \end{array}$

となるので $A$ は良い数列です。

yukicoder