自动搬运

查看原文

来自洛谷，原作者为

	MPLN 从无知走向更大的无知

搬运于2025-08-24 23:15:03，当前版本为作者最后更新于2025-04-28 09:53:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

推导题，难点在找到规律后推出公式，代码可以极为简洁地实现，也不需要二分之类。

（闲话：本文最后是挑战最短解的代码，欢迎大佬评论来爆）

思路

我们先观察 Kruskal 是怎么选边的：边权从小到大，如果两个端点没有连起来就选这条边。

所以我们也从小到大加边，过程中对于每条边贪心地：若存在点 $i,j$ 连通但是没有直接相连的边，就把它们连起来，然后这条边不会在 MST 里，成功浪费掉目前这个边权较小的边；否则就只能采用这条边将另外一个不连通的点连过来。

持续直到剩下的所有边都必须采用到 MST，否则就连不出连通图，就全部加到答案里。

选边规律

所以假设边足够时，先设 $k=1$，发现这个过程是：

1. 把当前 $k$ 个点连成完全图，浪费掉这些边权太小的边；
2. 现在无论怎么连都会在 MST 里面用到，就只能用这条边连一个没有进入并查集的点，然后 $k\gets k+1$；
3. 继续步骤 1。

假设边足够时，哪些边会被选呢？

1. 连 1 和 2，被选。$k=2$（此时 2 个点成完全图）。
2. 连 2 和 3，被选。$k=3$。
3. 连 1 和 3，不被选。$k=3$（此时 3 个点成完全图）。
4. 连 3 和 4，被选。$k=4$。
5. 连 1 和 4，不被选。$k=4$。
6. 连 2 和 4，不被选。$k=4$（此时 4 个点成完全图）。
7. 连 4 和 5，被选。$k=5$。
8. 连 1 和 5，不被选。$k=5$。
9. 连 2 和 5，不被选。$k=5$。
10. 连 3 和 5，不被选。$k=5$（此时 5 个点成完全图）。
11. 连 5 和 6，被选。$k=6$。
12. 连 1 和 6，不被选。$k=6$。
13. 连 2 和 6，不被选。$k=6$。
14. 连 3 和 6，不被选。$k=6$。
15. 连 4 和 6，不被选。$k=6$（此时 6 个点成完全图）。
16. 连 6 和 7，被选。$k=7$。
17. 连 1 和 7，不被选。$k=7$。
18. $\dots$

假设边足够时，被选的边固定在数列 $a$：$1,2,4,7,11,16,22\dots$ 不难发现是二阶等差数列，通项公式次数为 2。可以用解三元一次方程组等方式发现：

$$a_i=\frac{1}{2}i^2-\frac{1}{2}i+1$$

$a$ 的前 $n$ 项和可以用平方数列和，等差数列求和等公式来得到，具体是啥可以参考我的文章数列求和部分：

$$\begin{aligned} \sum_{i=1}^na_i&=\frac{(2n+1)(n+1)n}{12}-\frac{(n+1)n}{4}+n\\ &=\frac{(n-1)(n+1)n}{6}+n\\ &=\frac{(n^2+5)n}{6} \end{aligned} $$

计算答案

那么什么时候是边不足够呢？假设我们已经选了第 $a_x$ 条边，如果再用中间的边拼完全图然后选第 $a_{x+1}$ 条的话，剩余的边不足以连通所有 $n$ 个点，就不足够了。具体来说，此时边权最大的 $n-1-x$ 条边都可以用在最小生成树里。

接下来就是需要确定这个 $x$ 了，有不等式：

$$m-a_x(剩余边)\ge n-1-x(需要边)$$

化简得：

$$\frac{1}{2}x^2-\frac{3}{2}x-m+n\le 0$$

求根公式取正根向下取整即为 $x$。

此时首先计算答案中 $a_1$ 到 $a_x$ 得边权和，用之前的公式：

$$sum_1=\frac{(x^2+5)x}{6}$$

然后最大的 $n-1-x$ 条边边权和可以用等差数列求和公式得到：

$$sum_2=\frac{(2m-n+x+2)(n-1-x)}{2}$$

最终答案就是：

$$ans=sum_1+sum_2$$

实现

1. 解一元二次方程，确定 $x$。
2. 用 $x$ 计算答案。

So easy!

唯一注意的就是假如用 long long，计算分数时，必须先除以 $2$ 或者 $6$ 再取模。这怎么办，乘之前不取模不会溢出吗？那就先单独判断分子中的哪个因式可以除以分母（或者分母的因数，对于 $6$ 就先判断除以 $2$ 再除以 $3$）。或者用 __int128。这里两种方法都提供。

时间复杂度 $O(T\operatorname{log}n)$，瓶颈在于开根号。

int128 版：

#include<bits/stdc++.h>
#define l __int128
l M = 998244353, T, n, m;
signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        l x = 1.5 + sqrt(2.25 - 2 * (n - m));
        printf("%lld\n", ((x * x + 5) * x / 6 + (2 * m - n + x + 2) * (n - 1 - x) / 2) % M);
    }
    return 0;
}

目前最短解 int128 压行版（长度 205B）：

#import<bits/stdc++.h>
#define l __int128
l M=998244353,T,n,m;main(){scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);l x=1.5+sqrt(2.25-2*(n-m));printf("%lld\n",((x*x+5)*x/6+(2*m-n+x+2)*(n-1-x)/2)%M);}}

提交记录

另一 long long 实现（其实有很多可以省略的代码）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
int t, n, m;
int cal() {
    double a = 0.5, b = -1.5, c = -m + n;
    double res = (-b + sqrt(b * b - 4 * a * c)) / 2 / a;
    return (int) res;
}
void frac(int &a, int &b, int c) { // 取模前先除以
    if (a % c == 0) a /= c;
    else b /= c;
}
signed main() {
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld", &n, &m);
        int x = cal(), t1, t2, ans = 0;
        t1 = x * x + 5, t2 = x; // 第一部分答案（a_1 到 a_x）
        frac(t1, t2, 2), frac(t1, t2, 3);
        ans = (ans + (t1 % MOD * (t2 % MOD) % MOD)) % MOD;
        t1 = m + m - n + x + 2, t2 = n - 1 - x; // 第二部分答案（最后 n-1-x 条边权和）
        frac(t1, t2, 2);
        ans = (ans + (t1 % MOD * (t2 % MOD) % MOD)) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}