33OJ
登录 注册

#P17538. 音符方阵

    ID: 20179 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷月赛

音符方阵

背景

『你会忘记我吗?』

你突然这样问我,我不知道应该怎么回答。

我的记忆是有限的,至于一生都不会忘记的部分只有一个 n×nn \times n 的方阵,奢求能够把和你度过的所有时光全部镌刻其中显然是不可能了。但是我们一起合奏过的音符构成了若干音阶。如果能够记住这些音符,也许就能记住永远向往着自由,永远绽放着的你了。你的演奏实在是太特别,我绝对不可能记错的。

『不会忘记,即使是死也不会的。』

题目描述

给定一个 nn,构造一个 n×nn\times n 的矩阵 anna_{nn} 满足:

  • 对于矩阵中的所有元素 aija_{ij},满足 1≤aij≤n1\le a_{ij}\le n 且为整数。
  • 对于每个 11 到 nn 的整数 ii:
    • 存在且仅存在一行,使得这一行上所有 ii 的倍数列位置上出现的数都是 ii;
    • 存在且仅存在一列,使得这一列上所有 ii 的倍数行位置上出现的数都是 ii。

可以证明,至少存在一种符合要求的构造。如果有多种构造,你可以输出任意一种。

输入格式

本题包含多组测试。

对于每组数据,第一行一个整数 TT,表示测试数据组数。

对于每组测试数据,输入一行一个整数 nn,表示你要构造的方阵大小。

输出格式

对于每组数据,输出 nn 行,每行 nn 个用空格隔开的整数,表示你构造的方阵。

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

提示

样例 #1 解释

对于第一组数据:

  • 11 满足要求。因为第一行上所有 11 的倍数列位置((1,1),(1,2),(1,3),(1,4)(1,1),(1,2),(1,3),(1,4))上均为 11,第一列上所有 11 的倍数行位置((1,1),(2,1),(3,1),(4,1)(1,1),(2,1),(3,1),(4,1))上均为 11,并且没有其他行和列满足对应的要求。
  • 22 满足要求。因为第三行上所有 22 的倍数列位置((3,2),(3,4)(3,2),(3,4))上均为 22,第二列上所有 22 的倍数行位置((2,2),(4,2)(2,2),(4,2))上均为 22,并且没有其他行和列满足对应的要求。
  • 33 满足要求。因为第三行上所有 33 的倍数列位置((3,3)(3,3))上均为 33,第三列上所有 33 的倍数行位置((3,3)(3,3))上均为 33,并且没有其他行和列满足对应的要求。
  • 44 满足要求。因为第二行上所有 44 的倍数列位置((2,4)(2,4))上均为 44,第三列上所有 44 的倍数行位置((4,3)(4,3))上均为 44,并且没有其他行和列满足对应的要求。

所以这是一种符合要求的矩阵。

数据范围

本题开启捆绑测试。

对于 100%100\% 的数据,1≤T≤1001\le T\le 100,1≤∑n≤20001\le \sum n\le 2000。

子任务 ∑n≤\sum n\le 得分
1 88 2525
2 2020
3 20002000 5050