题目中说 \(n\) 个点的无向完全图有 \(\frac{n!}{2}\) 条哈密顿路径。如果我们考虑方向（即每条路径钦定起点终点）的话，一共就有 \(n!\) 条了，因为一条路径 \((u,v)\) 可以钦定 \(u\to v\) 或 \(v\to u\)。为了方便符号表达，以下都按照哈密顿路径数为 \(n!\) 即路径有向进行分析。
忘掉有关排列的东西，先冷静思考一下，\(n\) 个点的无向完全图的哈密顿路径数为啥是 \(n!\)。
事实上，可以考虑归纳证明。
- \(n=2\) 时，哈密顿路径数为 \(2\)（\(1\to 2\) 或者 \(2\to 1\)）。显然满足。
- \(n=k\) 时，若哈密顿路径数为 \(k!\)，下证 \(n=k+1\) 时，哈密顿路径数为 \((k+1)!\)。
考虑 \(k\) 个点的完全图，我们在其中插入一个点 \(k+1\)。随便拉出原图的一个哈密顿路径，这样的路径有 \(k!\) 种，假设为 \(P:\{u\to v\}\)，考虑新生成哈密顿路径 \(P'\) 的方式（记住这些方式，下面构造的证明要用到）：
- \(k+1\) 可以插到 \(v\) 后面变成路径的末尾，即 \(P':\{u\to v\to k+1\}\)。
- \(k+1\) 可以插到 \(u\) 前面变成路径的首位，即 \(P':\{k+1\to u\to v\}\)。
- 找到路径中间的一条边 \(w:i\to j\)，这样的边有 \(k-1\) 条，我们把这条边从 \(P\) 中删去，用 \(i\to k+1\) 和 \(k+1\to j\) 替换。即 \(P':\{u\to k+1\to v\}\)。
根据一条原有的路径新生成哈密顿路径的方案数为 \(1+1+(k-1)=k+1\) 种，那么新生成哈密顿路径的条数就是 \(k!\cdot (k+1)=(k+1)!\)。归纳得证。
然而这个结论对这道题并没有什么用这启示我们归纳构造。显然 \(n=2\) 时我们直接将 \(1\) 和 \(2\) 之间连权值为 \(1\) 的边即可。考虑 \(n=k\) 时我们构造出了合法的完全图，考虑插入 \(k+1\) 点：
将此时边权和最大的哈密顿路径的边权和记为 \(M\)，假如我们现在构造出一个序列 \(a\) 满足：
- \(\forall 1\le i<j\le k,a_i\neq a_j\)
- \(\forall 1\le i<j\le k,1\le x<y\le k,(i,j)\neq (x,y),a_i+a_j\neq a_x+a_y\)
- \(\forall 1\le i<j\le k,1\le x\le n,a_x\neq a_i+a_j\)
那么我们就可以将 \(k+1\) 向 \(1\le i\le k\) 的 \(i\) 连权值为 \((M+1)a_i\) 的边。我们把这样的边叫做新边。
这样的图是一定合法的，因为考虑一条新的哈密顿路径仅会经过新的边 \(1\) 或 \(2\) 次，而由于 \(M\) 的最大性，属于旧哈密顿路径的边边权和不超过 \(M\)，而 \(a\) 中任意至多 \(2\) 个数的和都至少差 \(1\)，那么：
- 如果两条新的哈密顿路径经过的新边相同，则它们属于原图的部分的边权和不同（这是因为由一开始的证明可知，如果经过两条新边的话，被新边“替换”的边和这个部分在原图形成哈密顿路径；如果经过一条的话，则原图内的部分就是原图的哈密顿路径），所以新的边权和也不同。
- 如果两条新的哈密顿路径经过的新边不同，它们属于原图部分的边权和 \(\le M\)，由于任意至多 \(2\) 条新边边权之和的两两差至少为 \(M+1\)（\(a\) 中任意至多 \(2\) 个数的和至少差 \(1\)），所以新的边权和也不同。
所以问题来到如何构造一个满足条件的序列 \(a\)，随便搜一下即可。构造出的 \(a\) 形如 \(\{1,2,4,7,12,20,29,38,52,73\}\)。
然后我们需要求一张完全图的哈密顿路径边权最大和，也是随便搜一下即可。构造出来 \(n=10\) 时最大的哈密顿路径边权和 \(M\) 大概是 \(9.68\times 10^{10}\)，题目 \(10^{11}\) 的限制还是挺充裕的。
const int N = 20;
int n, w[N][N], p[N], mx;
int a[N] = { 0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73 };
void gmx(int n) {
mx = 0;
for (int i = 1; i <= n; i++) p[i] = i;
do {
int res = 0;
for (int i = 2; i <= n; i++)
res += w[p[i]][p[i - 1]];
mx = max(mx, res);
} while (next_permutation(p + 1, p + n + 1));
}
bool chk(int n, int i) {
p[n] = i;
map<int, int> t;
for (int i = 1; i <= n; i++)
if (t.count(p[i])) return 0;
else t[p[i]] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (t.count(p[i] + p[j])) return 0;
else t[p[i] + p[j]] = 1;
return 1;
}
void dfs(int dep) {// Construct a[]
if (dep == 11) {
for (int i = 1; i <= 10; i++)
wr(p[i]), pc(' ');
exit(0);
}
for (int i = 1; ; i++) {
if (!chk(dep, i)) continue;
p[dep] = i;
dfs(dep + 1);
}
}
signed main() {
// dfs(1);
n = rd();
w[1][2] = w[2][1] = 1;
for (int i = 3; i <= n; i++) {
gmx(i - 1);
for (int j = 1; j < i; j++)
w[i][j] = w[j][i] = a[j] * (mx + 1);
}
for (int i = 1; i <= n; i++, puts(""))
for (int j = 1; j <= n; j++)
wr(w[i][j]), pc(' ');
return 0;
}