分数: 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