102517: [AtCoder]ABC251 Ex - Fill Triangle
Description
Score : $600$ points
Problem Statement
Blocks are stacked in a triangle. The $i$-th column from the top has $i$ blocks.
You are given a sequence $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$ which is a result of the run-length compression of a sequence $A = (A_1, A_2, ..., A_N)$ consisting of non-negative integers less than or equal to $6$.
- For example, when $A = (2, 2, 2, 5, 5, 1)$, you are given $P = ((2, 3), (5, 2), (1, 1))$.
You will write a number on each block so that the following conditions are satisfied, where $B_{i,j}$ denotes the number to write on the $j$-th block from the left in the $i$-th column from the top:
- For all integers $i$ such that $1 \leq i \leq N$, it holds that $B_{N,i} = A_{i}$.
- For all pairs of integers $(i, j)$ such that $1 \leq j \leq i \leq N-1$, it holds that $B_{i,j}= (B_{i+1,j}+B_{i+1,j+1})\bmod 7$.
Enumerate the numbers written on the blocks in the $K$-th column from the top.
What is run-length compression?
The run-length compression is a conversion from a given sequence $A$ to a sequence of pairs of integers obtained by the following procedure.- Split $A$ off at the positions where two different elements are adjacent to each other.
- For each subsequence $B$ that has been split off, replace $B$ with a integer pair of "the number which $B$ consists of" and "the length of $B$".
- Construct a sequence consisting of the integer pairs after the replacement without changing the order.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $K$ $a_1$ $c_1$ $a_2$ $c_2$ $\vdots$ $a_M$ $c_M$
Output
Print the answer in the following format. It is guaranteed that the answer is unique under the Constraint of the problem.
$B_{K,1}$ $B_{K,2}$ $\dots$ $B_{K,K}$
Sample Input 1
6 3 4 2 3 5 2 1 1
Sample Output 1
1 4 3 2
We have $A = (2,2,2,5,5,1)$. The number written on the blocks are as follows.
3
5 5
5 0 5
1 4 3 2
4 4 0 3 6
2 2 2 5 5 1
Sample Input 2
1 1 1 6 1
Sample Output 2
6
Sample Input 3
111111111 9 9 0 1 1 10 2 100 3 1000 4 10000 5 100000 6 1000000 0 10000000 1 100000000
Sample Output 3
1 0 4 2 5 5 5 6 3
Input
题意翻译
存在序列 $ a_n $，将其压缩后给定。具体地，给定序列 $ P $ 以如下形式：$ ((a_1, c_1), (a_2, c_2), \cdots, (a_m, c_m)) $，表示序列 $ a $ 中有 $ c_1 $ 个 $ a_1 $，$ c_2 $ 个 $ a_2 $，以此类推，且按序拼接。令序列 $ a_n $ 为三角金字塔 $ B $ 的第 $ n $ 层，即 $ B(n, i) = a_i $。特别地，该三角金字塔的递推式为 $ B(i, j) = (B(i + 1, j) + B(i + 1, j + 1)) \bmod{7} $。给定 $ k $，求该三角金字塔第 $ k $ 层的序列。Output
问题描述
有一堆三角形堆放的积木。从顶部算起的第i列有i个积木。
给你一个序列$P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$，它是序列$A = (A_1, A_2, ..., A_N)$经过运行长度压缩后的结果，其中$A$由不大于6的非负整数组成。
- 例如，当$A = (2, 2, 2, 5, 5, 1)$时，你将得到$P = ((2, 3), (5, 2), (1, 1))$。
你需要在每个积木上写一个数字，使得以下条件得到满足，其中$B_{i,j}$表示从顶部算起的第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$转换为一个整数对序列的过程，过程如下：- 在$A$中，在相邻的两个不同元素之间分割。
- 对于每个被分割出来的子序列$B$，用“$B$包含的数字”和“$B$的长度”组成的整数对替换$B$。
- 按照原来的顺序构造一个包含整数对的序列。
约束条件
- $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$
- 输入中的所有值都是整数。
输入
输入从标准输入中给出，格式如下：
$N$ $M$ $K$ $a_1$ $c_1$ $a_2$ $c_2$ $\vdots$ $a_M$ $c_M$
输出
按照如下格式输出答案。可以保证在问题的约束条件下，答案是唯一的。
$B_{K,1}$ $B_{K,2}$ $\dots$ $B_{K,K}$
样例输入1
6 3 4 2 3 5 2 1 1
样例输出1
1 4 3 2
我们有$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
样例输入2
1 1 1 6 1
样例输出2
6
样例输入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