AT_abc251_h [ABC251Ex] Fill Triangle

题目描述

有 $N$ 层的三角形状的方块。从上往下第 $i$ 层有 $i$ 个方块。

给定一个由不超过 $6$ 的非负整数组成的序列 $A = (A_1, A_2, ..., A_N)$，以及它的游程编码（Run-Length Encoding）序列 $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$。

• 例如，当 $A = (2, 2, 2, 5, 5, 1)$ 时，$P = ((2, 3), (5, 2), (1, 1))$。

对于每个方块，记从上往下第 $i$ 层、从左往右第 $j$ 个方块上写的数为 $B_{i,j}$，请按照以下条件为所有方块填写数字：

• 对于所有满足 $1 \leq i \leq N$ 的整数 $i$，有 $B_{N,i} = A_i$。
• 对于所有满足 $1 \leq j \leq i \leq N-1$ 的整数对 $(i, j)$，有 $B_{i,j} = (B_{i+1,j} + B_{i+1,j+1}) \bmod 7$。

请输出从上往下第 $K$ 层所有方块上写的数字。

什么是游程编码？
游程编码是将数列 $A$ 按照以下步骤转换为由整数对组成的序列的过程：

1. 在相邻元素不同的地方将 $A$ 分割成若干段。
2. 对于每一段 $B$，用“该段的数字”和“该段的长度”组成一个整数对替换该段。
3. 按原顺序排列所有整数对，得到新的序列。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $a_1$ $c_1$ $a_2$ $c_2$ $\cdots$ $a_M$ $c_M$

输出格式

请输出答案。保证在约束条件下答案唯一。

$B_{K,1}$ $B_{K,2}$ $\dots$ $B_{K,K}$

输入输出样例 #1

输入 #1

6 3 4
2 3
5 2
1 1

输出 #1

1 4 3 2

输入输出样例 #2

输入 #2

1 1 1
6 1

输出 #2

6

输入输出样例 #3

输入 #3

111111111 9 9
0 1
1 10
2 100
3 1000
4 10000
5 100000
6 1000000
0 10000000
1 100000000

输出 #3

1 0 4 2 5 5 5 6 3

说明/提示

约束条件

• $1 \leq N \leq 10^9$
• $1 \leq M \leq \min(N, 200)$
• $1 \leq K \leq \min(N, 5 \times 10^5)$
• $0 \leq a_i \leq 6$
• $1 \leq c_i \leq N$
• $\sum_{i=1}^M c_i = N$
• 所有输入的值均为整数

样例解释 1

$A = (2,2,2,5,5,1)$。各方块上的数字如下所示：

3
5 5
5 0 5
1 4 3 2
4 4 0 3 6
2 2 2 5 5 1

由 ChatGPT 4.1 翻译