题解 | #构造数独#

题目链接

题目描述

需要构造一个 $n \times n$ 的非负整数矩阵，使得该矩阵的每一行之和与每一列之和都等于一个给定的整数 $s$ 。如果不存在这样的矩阵，则输出 -1。

解题思路

这是一个构造性问题。虽然题目提到了可能无解（输出-1），但从数学上讲，只要行和的总和（ $n \cdot s$ ）等于列和的总和（ $n \cdot s$ ），就总能构造出这样一个非负整数矩阵。因此，对于所有正整数 $n, s$ ，本题总是有解的。

一个通用且能让矩阵内元素分布相对均匀的构造方法如下：

基础值分配：首先，我们将 $s$ 平均分配给 $n$ 个元素。每个元素可以先获得一个基础值，即 $s$ 整除 $n$ 的商 $q = s / n$ 。
余数分配：经过基础值分配后，每行/每列的和为 $n \cdot q$ 。我们还需要将总和的余数 $r = s \pmod n$ 分配下去，使得每行/每列的和都再增加 $r$ 。
循环对角线：我们可以通过在 $r$ 条不同的“循环对角线”上各加 $1$ 来实现余数的均匀分配。
构造公式：综合起来，我们可以用一个公式直接生成矩阵的每个元素 $a_{i,j}$ （行列均从0开始索引）： $a_{i,j} = (s/n) + (1 \text{ if } (j-i+n)\pmod n < (s\pmod n) \text{ else } 0)$

这个公式可以保证：

行和：对于任意一行 i，当 j 从 0 遍历到 n-1 时，(j-i+n)%n 的值会不重不漏地取遍 0, 1, ..., n-1。因此，条件 < s%n 会恰好成立 s%n 次。所以，该行的和为 $n \cdot (s/n) + (s \pmod n) \cdot 1 = s$ 。
列和：同理，对于任意一列 j，行 i 的变化也会让 (j-i+n)%n 取遍所有可能的值，保证列和也为 $s$ 。
非负性：由于 $s, n$ 均为正整数，所以商和余数都是非负的，构造出的元素也必然是非负的。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long s;
    cin >> n >> s;

    long long q = s / n;
    long long r = s % n;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long val = q;
            if ((j - i + n) % n < r) {
                val++;
            }
            cout << val << (j == n - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long s = sc.nextLong();

        long q = s / n;
        long r = s % n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long val = q;
                if ((j - i + n) % n < r) {
                    val++;
                }
                System.out.print(val + (j == n - 1 ? "" : " "));
            }
            System.out.println();
        }
    }
}

n, s = map(int, input().split())

q = s // n
r = s % n

matrix = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        val = q
        if (j - i + n) % n < r:
            val += 1
        matrix[i][j] = val

for row in matrix:
    print(*row)

算法及复杂度

算法：数学构造
时间复杂度： $\mathcal{O}(n^2)$ ，我们需要构造并输出一个 $n \times n$ 的矩阵。
空间复杂度： $\mathcal{O}(n^2)$ ，在 Python 版本中需要存储整个矩阵，C++/Java版本可以优化到 $\mathcal{O}(1)$ （如果直接计算并输出）。