算法竞赛题解

B - 最大生成树

题目大意 有一个 n 个点的完全图，点编号 1 \sim n ，点 (i, j) 之间的边权为 i - j 。求该图最大生成树的边权总和，对 998244353 取模。 2 \le n \le 10^{18} ，且 n 为偶数。 思路分析 完全图的边权只取决于两个端点的距离，直觉上应选"尽量长的边"。用 Kruskal…