Rectangular Congruence
Contest: Codeforces Round 822 (Div. 2)
Difficulty rating: 2100
Tags: constructive algorithms, number theory

You are given a prime number $$$n$$$, and an array of $$$n$$$ integers $$$b_1,b_2,\ldots, b_n$$$, where $$$0 \leq b_i < n$$$ for each $$$1 \le i \leq n$$$.

You have to find a matrix $$$a$$$ of size $$$n \times n$$$ such that all of the following requirements hold:

- $$$0 \le a_{i,j} < n$$$ for all $$$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$$$ for all positive integers $$$r_1$$$, $$$r_2$$$, $$$c_1$$$, and $$$c_2$$$ such that $$$1 \le r_1 < r_2 \le n$$$ and $$$1 \le c_1 < c_2 \le n$$$.
- $$$a_{i,i} = b_i$$$ for all $$$1 \le i \leq n$$$.

Here $$$x \not \equiv y \pmod m$$$ denotes that $$$x$$$ and $$$y$$$ give different remainders when divided by $$$m$$$.

If there are multiple solutions, output any. It can be shown that such a matrix always exists under the given constraints.

Input format:
The first line contains a single positive integer $$$n$$$ ($$$2 \le n < 350$$$).

The second line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i < n$$$) — the required values on the main diagonal of the matrix.

It is guaranteed that $$$n$$$ is prime.

Output format:
Print $$$n$$$ lines. On the $$$i$$$-th line, print $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$, each separated with a space.

If there are multiple solutions, output any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the answer is valid because all entries are non-negative integers less than $$$n = 2$$$, and $$$a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 2$$$ (because $$$a_{1,1}+a_{2,2} = 0 + 0 \equiv 0 \pmod 2$$$ and $$$a_{1,2}+a_{2,1} = 1 + 0 \equiv 1 \pmod 2 $$$). Moreover, the values on the main diagonals are equal to $$$0,0$$$ as required.

In the second example, the answer is correct because all entries are non-negative integers less than $$$n = 3$$$, and the second condition is satisfied for all quadruplets $$$(r_1, r_2, c_1, c_2)$$$. For example:

- When $$$r_1=1$$$, $$$r_2=2$$$, $$$c_1=1$$$ and $$$c_2=2$$$, $$$a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 3$$$ because $$$a_{1,1}+a_{2,2} = 1 + 1 \equiv 2 \pmod 3$$$ and $$$a_{1,2}+a_{2,1} = 2 + 1 \equiv 0 \pmod 3 $$$.
- When $$$r_1=2$$$, $$$r_2=3$$$, $$$c_1=1$$$, and $$$c_2=3$$$, $$$a_{2,1}+a_{3,3} \not\equiv a_{2,3}+a_{3,1} \pmod 3$$$ because $$$a_{2,1}+a_{3,3} = 1 + 1 \equiv 2 \pmod 3$$$ and $$$a_{2,3}+a_{3,1} = 0 + 1 \equiv 1 \pmod 3 $$$.

Example input:
2
0 0

Example output:
0 1 
0 0

Example input:
3
1 1 1

Example output:
1 2 2
1 1 0
1 0 1

Editorial:
We say a matrix to be good if it satisfies the congruence condition (the second condition).
When we have a good matrix, we can add any value $$$c$$$ to a whole row while maintaining the congruence relation. The same is true for adding the same value to a whole column.
Suppose we have any good matrix $$$A$$$, then by adding $$$b_i - a_{i,i}$$$ to the $$$i$$$-th row for each of $$$i=1,2,\cdots,n$$$, we obtain a good matrix that has the desired values on the diagonal.
In fact, there are a lot of possible constructions. We present a few of them here:
• $$$a_{i,j} = i \times j \pmod n$$$
• $$$a_{i,j} = (i + j)^2 \pmod n$$$. This needs special handling when $$$n=2$$$.
• $$$a_{i,j} = \frac{(i+j)(i+j+1)}{2} \pmod n$$$.
• The coolest part is that all quadratic polynomials in the form $$$ai^2 + bij + cj^2 + di + ej + f$$$ are valid for all integers $$$a,b,c,d,e,f$$$ and $$$b \not\equiv 0 \pmod n$$$
As a bonus, we prove that the general quadratic polynomial gives a good construction.
Since we can add values to a whole row or column, and $$$i^2, j^2 , i , j , 1$$$ are also constant on the rows and columns, adding them by $$$a_{i,j}$$$ has no effect. So we may just assume $$$a = c = d =e = f =0$$$.
So it suffices to show that $$$a_{i,j} = b i j \pmod n$$$ satisfies the condition. We can see directly that $$$a_{r_1,c_1} - a_{r_2,c_1} - a_{r_1,c_2} +a_{r_2,c_2} = b(r_1 - r_2)(c_1 - c_2)$$$. As $$$r_1 \neq r_2$$$, $$$c_1 \neq c_2$$$, $$$b \not\equiv 0 \pmod n$$$, and $$$n$$$ is a prime, this expression must be nonzero $$$\pmod n$$$.
Here are some extra observations that may enable one to find a good matrix more quickly.
For each $$$j$$$, the values $$$a_{i,j} - a_{i-1,j}$$$ over all $$$0 \le i <n $$$ must be a permutation of $$$\{0,1,\cdots,n-1\}$$$.
A good matrix stays good if we permute the rows or permute the columns. Therefore, we can show that there exists some good matrix with $$$a_{1,j} = a_{i,1} = 0$$$, and $$$a_{2,j} = j-1$$$, $$$a_{i,2} = i-1$$$. Assuming this, it should not be difficult to discover $$$a_{i,j} = (i-1)(j-1)$$$ yields one of the good matrices.
Let $$$b$$$ be the two dimensional difference array of $$$a$$$, that is, $$$b_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}$$$. Then, the condition becomes sum of any rectangles of $$$b$$$ must be nonzero $$$\pmod n$$$. It is easy to see $$$ b = 1$$$ is valid. This corresponds to the solution that $$$a_{i,j} = i \times j \pmod n$$$.