← 返回题目列表

AtCoder · arc107_e

E. 墨西哥垫

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

考虑 N \times N 矩阵。让我们表示为 a_{i, j} 中的条目 i第行和 j- 第列。对于 a_{i, j} 其中 i=1 or j=1 成立,其值为以下之一 0, 1 和 2 并在输入中给出。其余条目定义如下:

  • a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N) 其中 \mathrm{mex}(x, y) 由下表定义:
\mathrm{mex}(x, y) y=0 y=1 y=2
x=0 1 2 1
x=1 2 0 0
x=2 1 0 0

矩阵有多少个条目 输入中给出的 0, 1, 和 2分别是?

约束

  • 1 \leq N \leq 500{,}000
  • a_{i,j}是以下之一 0, 1 和 2.

输入

输入由标准输入按以下格式给出:

N
a_{1, 1} a_{1, 1} ... a_{1, N}
a_{2, 1}
:
a_{N, 1}

输出

打印数量 0的, 1的,和 2由空格分隔。


示例输入 1

4
1 2 0 2
0
0
0

示例输出 1

7 4 5

矩阵如下:

1 2 0 2
0 1 2 0
0 2 0 1
0 1 2 0