人类智慧题, 然而我是蒟蒻 qwq.
题目
X 国经历了一场前所未有的大地震，人们伤痕累累，整个国家破碎不堪。
为了帮助人们痊愈，也为了让 X 国能够生存下去，X 国国王决定重建 X 国。
国王决定先建造 \(n\) 座城市，由于国王喜欢奇数，所以 \(n\) 为奇数。
城市建造完后，需要给每两座城市之间都修建一条道路，即一共需要修建 \(\frac{n(n-1)}{2}\) 条道路。
不过，修建双向道路的成本太高了，建造完 \(n\) 座城市后剩下的经费最多只够修建 \(n\) 条双向道路，而其余的道路只能修建成单向的。好在方向并不会影响修建单向道路所需的费用，因此所有单向道路的方向可以任意决定。
另外，等到重建完成后，国王决定将 \(4\) 座城市钦定为 X 国的核心城市。为促进 X 国的发展，这 \(4\) 座核心城市中的任意两座城市，必须能够在不经过非核心城市的情况下相互到达。
国王希望，你能够给他一种道路修建方案，使重建完成后选择 \(4\) 座核心城市的方案数最大化。
分析
首先应该要想到 4 个点且两两之间有一条边是很容易形成强联通分量的, 因此我们要考虑最小化不形成强连通分量的方案数.
先找到 4 个点不形成强连通分量的情况. 直接枚举连边需要枚举 \(2^4 = 16\) 种情况, 而点只有 \(4\) 个, 因此我们应该考虑枚举被孤立的点数:
- 1 个结点被孤立: 该结点出度/入度为 \(3\)
- 2 个结点被孤立: 4 个结点分为两组, 每组 2 个结点, 两组之间只存在单向连边
注意上面列出的 3 种情况的任意组合都可能同时出现.
不妨先考虑减少第 1 种情况: 一个结点向其它 3 个结点各连一条有向边.
假设结点 \(i\) 的出度为 \(d_{i}\), 那么结点 \(i\) 能形成的方案数为 \({d_{i}\choose{3}} = \frac{d_{i}(d_{i} - 1)(d_{i} - 2)}{6}\), 我们希望 \(\sum_{i=1}^{n}{d_{i}\choose 3}\) 尽可能小, 而根据题意, 所有结点的出度之和为 \(\sum_{i=1}^{n}d_{i}=\frac{n(n-1)}{2}-n = \frac{n(n-3)}{2}\), 相当于我们找一个 \(d\) 的分配方案使得 \(\sum_{i=1}^{n}{d_{i}\choose 3}\) 最小.
令 \(f(x) = \frac{x (x - 1)(x - 2)}{6}\), 求导得 \(f^{\prime}(x) = \frac{3x^{2} - 6x + 2}{6} = \frac{3(x-1)^{2} - 1}{6}\), 当 \(x \geq 2\) 时 \(f^{\prime}(x)>0\) 为下凸函数, 因此每个结点的出度相等时 \(\sum_{i=1}^{n}{d_{i}\choose 3}\) 最小, 为 \(n \cdot {\frac{n-3}{2} \choose 3} = \frac{n(n-3)(n-5)(n-7)}{48}\).
由于第 1 种情况可以包含后面 2 种情况, 我们不妨思考能否通过构造使得后面 2 种情况不会单独出现. 事实上, 答案是可以的 (反正我想不到就是了 /dk).
对于这种 \(n\) 个点没有什么不同的情形, 一般情况下每个点 treat the same 就会得到最优解. 因此, 我们先试着把 \(n\) 条无向边给每个结点 2 条 (每个结点连出一条, 然后被连入一条, 但都是无向边), 将 \(n\) 个结点看作分布在圆上的正 \(n\) 边形的顶点, \(n\) 为奇数所以每个结点分别与它所在直径左右两侧最近的结点连一条无向边, 此时 2 条无向边将其余 \(n-3\) 个结点平均分为了两边, 我们将当前结点的出边连向右边的 \(\frac{n-3}{2}\) 个结点, \(n\) 个结点都这样连完之后会发现所有连入这个结点的边只会从左边的 \(\frac{n-3}{2}\) 个结点出发.
可以发现这种构造满足了只有第 1 种情况才会单独出现, 同时第 1 种情况的方案数最少, 从而我们得到了最终答案: \({n\choose 4} - \frac{n(n-3)(n-5)(n-7)}{48} = \frac{n(n-3)(n^{2} + 6n - 31)}{48}\).
代码
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 n;
std::cin >> n;
if (n == 1) {
std::cout << "0\n0";
return 0;
}
std::cout << n * (n - 3) * (n * n + 6 * n - 31) / 48 << "\n";
int m = (n + 1) / 2;
for (int i = 0; i < n; ++i) {
std::vector<int> g(n, 0);
for (int j = 1; j <= m; ++j) {
g[(i + j) % n] = 1;
}
for (int j = 0; j < n; ++j) {
std::cout << g[j] << " ";
}
std::cout << "\n";
}
return 0;
}