問題一覧 > 通常問題

No.2663 Zero-Sum Submatrices

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 136
作問者 : suisen / テスター : 👑 p-adic cureskol ygussany
お気に入りにしたユーザー ProblemId : 8957 / 自分の提出
問題文最終更新日: 2024-02-29 21:39:14
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 420 (順位表) の他の問題:

Problem Statement

You are given positive integers $n, m$. Construct a $2 ^ n \times 2 ^ m$ matrix $A=(a_{i,j})_{1\leq i\leq 2^n,1\leq j\leq 2^m}$ satisfying all of the following conditions.

  • Each integer at least $0$ and less than $2 ^ {n + m}$ appears in $A$ exactly $1$ time.
  • For all integers $i,j,k,l$ such that $1\leq i\lt j \leq 2 ^ n, 1\leq k\lt l \leq 2 ^ m$, it holds that $a _ {i, k} \oplus a _ {i, l} \oplus a _ {j, k}\oplus a _ {j, l} = 0$. Here, $x\oplus y$ denotes the bitwise XOR of $x$ and $y$.

If no such $A$ exists, report that fact.

Input

The input is given from standard input in the following format.

$n\ m$
  • All inputs are integers
  • $1\leq n$
  • $1\leq m$
  • $n + m \leq 12$

Output

If an $A$ satisfying the conditions exists, on line $i\ (1\leq i\leq 2 ^ n)$ print $a _ {i, 1}, a _ {i, 2}, \ldots, a _ {i, 2 ^ m}$ in this order, separated by spaces. Print a newline after the last line as well. If there are multiple $A$ satisfying the conditions, you may print any of them.

If no $A$ satisfying the conditions exists, print -1 on line $1$, followed by a newline.

Sample

Sample 1
Input
1 2
Output
2 6 1 5
0 4 3 7

Regarding condition $1$, every integer at least $0$ and less than $2 ^ {1 + 2} = 8$ indeed appears $1$ time each.

Condition $2$ also indeed holds, as follows.

  • [When $(i,j,k,l)=(1,2,1,2)$] $a _ {1, 1} \oplus a _ {1, 2} \oplus a _ {2, 1}\oplus a _ {2, 2} = 2 \oplus 6 \oplus 0\oplus 4 = 0$
  • [When $(i,j,k,l)=(1,2,1,3)$] $a _ {1, 1} \oplus a _ {1, 3} \oplus a _ {2, 1}\oplus a _ {2, 3} = 2 \oplus 1 \oplus 0\oplus 3 = 0$
  • [When $(i,j,k,l)=(1,2,1,4)$] $a _ {1, 1} \oplus a _ {1, 4} \oplus a _ {2, 1}\oplus a _ {2, 4} = 2 \oplus 5 \oplus 0\oplus 7 = 0$
  • [When $(i,j,k,l)=(1,2,2,3)$] $a _ {1, 2} \oplus a _ {1, 3} \oplus a _ {2, 2}\oplus a _ {2, 3} = 6 \oplus 1 \oplus 4\oplus 3 = 0$
  • [When $(i,j,k,l)=(1,2,2,4)$] $a _ {1, 2} \oplus a _ {1, 4} \oplus a _ {2, 2}\oplus a _ {2, 4} = 6 \oplus 5 \oplus 4\oplus 7 = 0$
  • [When $(i,j,k,l)=(1,2,3,4)$] $a _ {1, 3} \oplus a _ {1, 4} \oplus a _ {2, 3}\oplus a _ {2, 4} = 1 \oplus 5 \oplus 3\oplus 7 = 0$

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