CF1734E Rectangular Congruence 题解

题意：

给定一个质数 $n$（$n \leq 350$）和一个序列 $b_1, b_2, …, b_n$（对于 $\forall i$ 有 $0 \leq b_i < n$），你需要构造一个 $n \times n$ 的矩阵 $a$，满足：

对于 $\forall i, j \leq n$ 有 $0 \leq a_{i, j} < n $。

对于 $\forall 1 \leq r_1 \leq r_2 \leq n, 1 \leq c_1 \leq c_2 \leq n$ 有 $a_{r1, c1} + a_{r2, c2} \not\equiv a_{r1, c2} + a_{r2, c1} \pmod n $。

对于 $\forall 1 \leq i \leq n, 1 \leq c_1 \leq c_2 \leq n$ 有 $ a_{i, i} = b_i $。

输入格式：

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.

输出格式：

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.

集训时候讲的🐮🍺构造题，正如题解所说「思维难度 $\gg$ 代码难度」

依次考虑每个条件：

第一个条件，好像没限制太多，只需要我们构造的矩阵在模 $n$ 意义下仍然合法即可。
第二个条件，我们可以发现：
$\begin{aligned} &a_{x_1, y_1}+a_{x_2, y_2} \neq a_{x_1, y_2}+a_{x_2, y_1} \\[4pt]\Leftrightarrow \quad& a_{x_1, y_1}-a_{x_1, y_2} \neq a_{x_2, y_1}-a_{x_2, y_2} \end{aligned}$
这意味着矩阵的每两行对应位置的两个元素之差皆不相等。我们不妨令 $a_{i,j} = ij$ ，则
$a=\left[\begin{array}{ccccc} 1 & 2 & 3 & \cdots & n \\ 2 & 4 & 6 & \cdots & 2 n \\ 3 & 6 & 9 & \cdots & 3 n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & 2 n & 3 n & \cdots & n^2 \end{array}\right]$
暂且不考虑第三个条件，这个构造在模 $n$ 意义下是符合题意的。我们不妨代入试试
$\begin{aligned} &x_1y_1 + x_2y_2\ne x_1y_2 + x_2y_1 \\[4pt]\Leftrightarrow \quad & (x_1- x_2)(y_1 - y_2) \ne 0 \end{aligned}$
因为 $n$ 为质数，所以 $(x_1-x_2)$ 和 $(y_1-y_2)$ 均与 $n$ 互质，则
$(x_1- x_2)(y_1 - y_2) \not\equiv 0 \pmod{n}$
至此第一个条件也被满足了。
第三个条件，由于
$\begin{aligned} &a_{x_1, y_1}+a_{x_2, y_2} \neq a_{x_1, y_2}+a_{x_2, y_1} \\[4pt]\Leftrightarrow \quad&(a_{x_1, y_1} + c)+a_{x_2, y_2} \neq (a_{x_1, y_2} + c)+a_{x_2, y_1} \end{aligned}$
也就是说，使一行内的每个数同时加上 $c$ 没有影响。

那么问题就好办了，我们让第 $i$ 行的所有元素加上 $b_i - i^2$ 即可（模 $n$ 意义下）

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(666))

int n,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cout << ((i * j + a[i] - i * i) % n + n) % n << " \n"[j == n];
    return 0;
}