Odd Sum Rectangles
题意翻译
有一个 $2^N-1$ 行 $2^M-1$ 列的矩阵,矩阵每一个位置上有一个数,这个数只能是 $0$ 或 $1$。
构造这个矩阵,使得它的所有连续子矩阵中尽可能多的子矩阵中数的和为奇数,若有多种构造方式满足这一点,输出任意一个方案。
题目描述
[problemUrl]: https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_e
$ (2^N\ -\ 1) $ 行 $ (2^M-1) $ 列のグリッドがあり、 あなたはこれからすべてのマスに $ 0,\ 1 $ のいずれかの数字を書き込みます。 上から $ i $ 行目、左から $ j $ 列目に書き込む数字を $ a_{i,j} $ とします。
$ 1\leq\ i_1\ \leq\ i_2\leq\ 2^N-1,\ 1\leq\ j_1\ \leq\ j_2\leq\ 2^M-1 $ をみたす整数の組 $ (i_1,\ i_2,\ j_1,\ j_2) $ に対し、 $ S(i_1,\ i_2,\ j_1,\ j_2)\ =\ \displaystyle\ \sum_{r=i_1}^{i_2}\sum_{c=j_1}^{j_2}a_{r,c} $ と定義し、 さらに、グリッドの「奇妙さ」を $ S(i_1,\ i_2,\ j_1,\ j_2) $ が奇数となるような $ (i_1,\ i_2,\ j_1,\ j_2) $ の個数 と定義します。
奇妙さが最大となるような数字の書き込み方を $ 1 $ つ求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $
输出格式
奇妙さが最大となる書き込み方の $ 1 $ つを、以下の形式で出力せよ。
> $ a_{1,1}a_{1,2}\cdots\ a_{1,2^M-1} $ $ a_{2,1}a_{2,2}\cdots\ a_{2,2^M-1} $ $ \vdots $ $ a_{2^N-1,1}a_{2^N-1,2}\cdots\ a_{2^N-1,2^M-1} $
输入输出样例
输入样例 #1
1 2
输出样例 #1
111
说明
### 制約
- $ N,\ M $ は $ 1 $ 以上 $ 10 $ 以下の整数
### Sample Explanation 1
$ S(1,\ 1,\ 1,\ 1) $、$ S(1,\ 1,\ 2,\ 2) $、$ S(1,\ 1,\ 3,\ 3) $、$ S(1,\ 1,\ 1,\ 3) $ が奇数となるため、このグリッドの奇妙さは $ 4 $ です。 奇妙さを $ 5 $ 以上にすることはできないため、これは奇妙さが最大となる書き込み方の $ 1 $ つです。