← 返回题目列表

Codeforces · 1734/E

E. 矩形全等

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

给定一个素数 $$$n$$$ 和一个 $$$n$$$ 整数数组 $$$b_1,b_2,\ldots, b_n$$$,其中 $$$0 \leq b_i < n$$$ 对于每个 $$$1 \le i \leq n$$$。

你必须找到一个大小为 $$$n \times n$$$ 的矩阵 $$$a$$$ ,并且满足以下所有要求:

- $$$0 \le a_{i,j} < n$$$ 对于所有 $$$1 \le i, j \le n$$$。
- $$$a_{r_1, c_1} + a_{r_2, c_2} \not\equiv a_{r_1, c_2} + a_{r_2, c_1} \pmod n$$$ 对于所有正整数 $$$r_1$$$, $$$r_2$$$, $$$c_1$$$, 和$$$c_2$$$ 使得 $$$1 \le r_1 < r_2 \le n$$$ 和 $$$1 \le c_1 < c_2 \le n$$$。
- $$$a_{i,i} = b_i$$$ 对于所有 $$$1 \le i \leq n$$$。

这里 $$$x \not \equiv y \pmod m$$$ 表示 $$$x$$$ 和 $$$y$$$ 除以 $$$m$$$ 时得到不同的余数。

如果有多个解,则输出任意一个。可以证明,在给定的约束下,这样的矩阵总是存在的。

输入

第一行包含一个正整数 $$$n$$$ ($$$2 \le n < 350$$$)。

第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i < n$$$) - 矩阵主对角线上所需的值。

保证 $$$n$$$ 是素数。

输出

打印 $$$n$$$ 行。在第 $$$i$$$ 行,打印 $$$n$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$,每个整数之间用空格分隔。

如果有多个解,则输出任意一个。

示例

输入 #1

2
0 0

输出 #1

0 1 
0 0

输入 #2

3
1 1 1

输出 #2

1 2 2
1 1 0
1 0 1

输入 #3

5
1 4 1 2 4

输出 #3

1 0 1 3 4
1 4 3 1 0
2 4 1 0 2
1 2 2 2 2
2 2 0 1 4

注意

在第一个示例中,答案是有效的,因为所有条目都是小于 $$$n = 2$$$ 的非负整数,并且 $$$a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 2$$$ (因为 $$$a_{1,1}+a_{2,2} = 0 + 0 \equiv 0 \pmod 2$$$ 和 $$$a_{1,2}+a_{2,1} = 1 + 0 \equiv 1 \pmod 2 $$$)。此外,根据要求,主对角线上的值等于$$$0,0$$$。

在第二个示例中,答案是正确的,因为所有条目都是小于 $$$n = 3$$$ 的非负整数,并且所有四元组 $$$(r_1, r_2, c_1, c_2)$$$ 都满足第二个条件。例如:

- 当 $$$r_1=1$$$、$$$r_2=2$$$、$$$c_1=1$$$ 和 $$$c_2=2$$$ 时,$$$a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 3$$$ 因为$$$a_{1,1}+a_{2,2} = 1 + 1 \equiv 2 \pmod 3$$$ 和 $$$a_{1,2}+a_{2,1} = 2 + 1 \equiv 0 \pmod 3 $$$。
- 当 $$$r_1=2$$$、$$$r_2=3$$$、$$$c_1=1$$$ 和 $$$c_2=3$$$ 时,$$$a_{2,1}+a_{3,3} \not\equiv a_{2,3}+a_{3,1} \pmod 3$$$ 因为$$$a_{2,1}+a_{3,3} = 1 + 1 \equiv 2 \pmod 3$$$ 和 $$$a_{2,3}+a_{3,1} = 0 + 1 \equiv 1 \pmod 3 $$$。