分数: 900 点
问题陈述
Diverta City 是一个新城市,由 N 城镇编号 1, 2, ..., N.
市长林戈计划用一条双向道路连接每对两个不同的城镇。每条路的长度尚未确定。
A 哈密顿路径 是一条从其中一个城镇开始并访问其他每个城镇一次的路径。 哈密顿路径的反转被认为与原始哈密顿路径相同。
有 N! / 2 哈密顿路径。林戈希望所有这些路径都有不同的总长度(一条路径上道路长度的总和),以使城市多样化。
在以下条件下找到一组这样的道路长度:
- 每条道路的长度必须是正整数。
- 哈密顿路径的最大总长度必须最多为 10^{11}.
约束
- N 是介于 2 和 10 (含)。
输入
输入由标准输入按以下格式给出:
N
输出
按以下格式打印一组满足目标的道路长度:
w_{1, 1} \ w_{1, 2} \ w_{1, 3} \ ... \ w_{1, N}
w_{2, 1} \ w_{2, 2} \ w_{2, 3} \ ... \ w_{2, N}
: : :
w_{N, 1} \ w_{N, 2} \ w_{N, 3} \ ... \ w_{N, N}
其中 w_{i, j} 是连接城镇的道路长度 i 和镇 j,必须满足以下条件:
- w_{i, i} = 0
- w_{i, j} = w_{j, i} \ (i \neq j)
- 1 \leq w_{i, j} \leq 10^{11} \ (i \neq j)
如果存在多组满足目标的道路长度,则将接受其中任何一组。
示例输入 1
3
示例输出 1
0 6 15 6 0 21 15 21 0
存在三个哈密顿路径。这些路径的总长度如下:
- 1 → 2 → 3:总长度为 6 + 21 = 27.
- 1 → 3 → 2:总长度为 15 + 21 = 36.
- 2 → 1 → 3:总长度为 6 + 15 = 21.
它们是不同的,因此达到了目标。
示例输入 2
4
示例输出 2
0 111 157 193 111 0 224 239 157 224 0 258 193 239 258 0
有 12 哈密顿路径,具有不同的总长度。