102541: [AtCoder]ABC254 B - Practical Computing

Problem Statement

Find the $N$ integer sequences $A_0,\ldots,A_{N-1}$ defined as follows.

• For each $i$ $(0\leq i \leq N-1)$, the length of $A_i$ is $i+1$.
• For each $i$ and $j$ $(0\leq i \leq N-1, 0 \leq j \leq i)$, the $(j+1)$-th term of $A_i$, denoted by $a_{i,j}$, is defined as follows.
  • $a_{i,j}=1$, if $j=0$ or $j=i$.
  • $a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$, otherwise.

Constraints

• $1 \leq N \leq 30$
• $N$ is an integer.

Input

Input is given from Standard Input in the following format:

$N$

Output

Print $N$ lines. The $i$-th line should contain the terms of $A_{i-1}$ separated by spaces.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

问题描述

找出定义如下的一组整数序列$A_0,\ldots,A_{N-1}$。

• 对于每个$i$ $(0\leq i \leq N-1)$，$A_i$的长度为$i+1$。
• 对于每个$i$和$j$ $(0\leq i \leq N-1, 0 \leq j \leq i)$，$A_i$的第$(j+1)$项，记作$a_{i,j}$，定义如下。
  • 如果$j=0$或$j=i$，则$a_{i,j}=1$。
  • 否则，$a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$。

约束条件

• $1 \leq N \leq 30$
• $N$为整数。

输入

从标准输入以以下格式给出输入：

$N$

输出

打印$N$行。第$i$行应包含以空格分隔的$A_{i-1}$的项。

样例输入1

3

样例输出1

1
1 1
1 2 1

样例输入2

10

样例输出2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1