Start of the season

· · 题解

CF12E 题解

首先，看看样例里面给出的矩阵：

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

我们将 0 和所在行列的数换一下，矩阵如下：

2 1 3
1 3 2
3 2 1

我们可以看到这是一个满足 2,3 条件的 \left(n-1\right)\times\left(n-1\right) 的矩阵。

我们不妨反过来想，我们先构造这样一个奇数矩阵，现在我们需要其对角线为 0，将对角线改为 0 之后，矩阵依旧满足条件 2。
然而我们需要偶数矩阵，可以将对角线上的进行平移，一定满足每行（向右平移），每列（向下平移），这时我们只需要要求矩阵对角线上的数字互不相同即可。

所以，现在我们来想办法构造一个矩阵（如第 2 个矩阵），其满足主对角线上的数互不相同，并且满足条件 2,3 的奇数边长矩阵。

这个时候，我们会想到一种简单的构造方法——滚动全排列！

全排列，顾名思义，就是 1\sim n 打乱后重新组成的一个 n 个元素的数列。我们让第一行为最小的全排列即 1,2,...,n，然后让这个数列滚动起来，比如，第 i 行，i,i+1,...,n,1,2,...,i-1 就可以啦！

这是行列互不相等且以对角线为轴对称矩阵的构造质之一，对于这里每 1 行每 i 列都是一个全排列，但是这种代码并不好写，但是我先给出：

for(int i = 1;i <= n;i++)
{
    int k = 1;
    for(int j = i;j <= n;j++)
    {
        a[i][k] = j;
        k++;
    }
    for(int j = 1;j < i;j++)
    {
        a[i][k] = j;
        k++;
    }
}

现在，我们来看一个比较易写的结论，a[i][j] = (i + j) mod n + 1。

我们验证一下这个结论：（涉及一些数论基础内容，可以跳过）
对于 a[i][i]，其值为 2\times i，根据一点点数论知识，我们知道它们构成了一个模 n 的完全剩余系，所以各不相同；
对于对角线对称的点，他们的行数和列数互换，其和不变，故满足；
对于同行同列的点，其行数或列数相等，另一个行数或列数各不相同，其和为 n 个连续正整数，也构成模 n 的完全剩余系，也满足。

注意：我们要满足里面没有 0，所以必须加上 1。

这样一个满足条件 2,3 的奇数边长矩阵就写好了。

现在可以将主对角线的数平移了：
a[i][n] = a[n][i] = a[i][i];

再修改主对角线的数为 0：
a[i][i] = 0;

题目到这里就写完了，提供代码： 

#include <bits/stdc++.h>
using namespace std;

int a[1005][1005];
int sum;

int main()
{
    int n;
    cin >> n;
    n--;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            a[i][j] = (i + j) % n + 1;
        }
    }
    n++;
    for(int i = 1;i <= n;i++)
    {
        a[i][n] = a[i][i];
        a[n][i] = a[i][i];
        a[i][i] = 0;
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

最后，补充一下，如果要求 n 为奇数。
同理，可以构造边长为偶数的全排列矩阵，再平移加改 0 即可。