問題一覧 > 教育的問題

No.2442 Linear Map

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 64
作問者 : 👑 p-adic / テスター : t98slider
お気に入りにしたユーザー ProblemId : 9634 / 自分の提出
問題文最終更新日: 2026-10-23 08:17:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 402 (順位表) の他の問題:

Problem Statement

You are given as input a non-negative integer $N$ and a sequence $A$ of length $2^N$ consisting only of non-negative integers less than $2^{64}$.

 

First, we introduce some notation and terminology. For a non-negative integer $i$ less than $2^N$, we denote the $1+i$-th element of $A$ by $A_i$.

For non-negative integers $i, j$, we denote the bitwise exclusive OR of $i$ and $j$ by $i \textrm{ XOR } j$:

Here is an explanation for those who are not familiar with bitwise exclusive OR. (Click to expand)

 

$i \textrm{ XOR } j$ is the unique non-negative integer $k$ satisfying the following condition.

  • For any non-negative integer $d$,
    • if the $2^d$ digits of $i$ and $j$ in binary notation are equal, the $2^d$ digit of $k$ in binary notation is $0$.
    • if the $2^d$ digits of $i$ and $j$ in binary notation are not equal, the $2^d$ digit of $k$ in binary notation is $1$.

Here, for each pair of non-negative integers $n$ and $d$, the $2^d$ digit of $n$ in binary notation means the remainder when the quotient of $n$ divided by $2^d$ is divided by $2$.

 

$A$ is said to be a good sequence if it satisfies the following condition:

  • For any non-negative integers $i, j$ less than $2^N$, $A_{i \textrm{ XOR } j} = A_i \textrm{ XOR } A_j$.

 

Determine whether $A$ is a good sequence.

Background

First, for a non-negative integer $n$, the set of all non-negative integers less than $2^n$ can be identified with the linear space $\mathbb{F}_2^n$ over the field with $2$ elements $\mathbb{F}_2$, by considering the binary notation of each element. Roughly speaking, for those who do not know linear algebra, $\mathbb{F}_2^n$ is the set of all sequences of length $n$ consisting only of $0$ or $1$ (or terms identified with them).

$A$ being a good sequence is equivalent to the map $\mathbb{F}_2^N \to \mathbb{F}_2^{64}$ determined by $A$ under the above identification (a function that takes an element of $\mathbb{F}_2^N$ and returns an element of $\mathbb{F}_2^{64}$) being a linear map. Therefore, this problem is equivalent to determining whether a given map $\mathbb{F}_2^N \to \mathbb{F}_2^{64}$ is a linear map.

Input

The input is given from standard input in $1 + 2^N$ lines in the following format:

  • The $1$ st line contains $N$.
  • For each non-negative integer $i$ less than $2^N$, the $2 + i$-th line contains $A_i$.
$N$
$A_0$
$\vdots$
$A_{2^N-1}$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $0 \leq N \leq 17$.
  • For any non-negative integer $i$ less than $2^N$, $A_i$ is an integer satisfying $0 \leq A_i < 2^{64}$.

Output

Print Yes if $A$ is a good sequence, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
0
0
Output
Yes

$A = (0)$. The only non-negative integer less than $2^N = 2^0 = 1$ is $0$, and

$\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} $

hold, so $A$ is a good sequence.

Sample 2
Input
0
1
Output
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} $

hold, so $A$ is not a good sequence.

Sample 3
Input
1
2
1
Output
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} $

hold, so $A$ is not a good sequence.

Sample 4
Input
2
0
1
0
1
Output
Yes

$A = (0,1,0,1)$. The non-negative integers less than $2^N = 2^2 = 4$ are only the $4$ integers $0,1,2,3$, and

$\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} $

hold, so $A$ is a good sequence.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。