题解：P12375 「LAOI-12」MST?
MPLN
·
·
题解
推导题，难点在找到规律后推出公式，代码可以极为简洁地实现，也不需要二分之类。
（闲话：本文最后是挑战最短解的代码，欢迎大佬评论来爆）
思路
我们先观察 Kruskal 是怎么选边的：边权从小到大，如果两个端点没有连起来就选这条边。
所以我们也从小到大加边，过程中对于每条边贪心地：若存在点 i,j 连通但是没有直接相连的边，就把它们连起来，然后这条边不会在 MST 里，成功浪费掉目前这个边权较小的边；否则就只能采用这条边将另外一个不连通的点连过来。
持续直到剩下的所有边都必须采用到 MST，否则就连不出连通图，就全部加到答案里。
选边规律
所以假设边足够时，先设 k=1，发现这个过程是：
- 把当前 k 个点连成完全图，浪费掉这些边权太小的边；
- 现在无论怎么连都会在 MST 里面用到，就只能用这条边连一个没有进入并查集的点，然后 k\gets k+1；
- 继续步骤 1。
假设边足够时，哪些边会被选呢？
- 连 1 和 2，被选。k=2（此时 2 个点成完全图）。
- 连 2 和 3，被选。k=3。
- 连 1 和 3，不被选。k=3（此时 3 个点成完全图）。
- 连 3 和 4，被选。k=4。
- 连 1 和 4，不被选。k=4。
- 连 2 和 4，不被选。k=4（此时 4 个点成完全图）。
- 连 4 和 5，被选。k=5。
- 连 1 和 5，不被选。k=5。
- 连 2 和 5，不被选。k=5。
- 连 3 和 5，不被选。k=5（此时 5 个点成完全图）。
- 连 5 和 6，被选。k=6。
- 连 1 和 6，不被选。k=6。
- 连 2 和 6，不被选。k=6。
- 连 3 和 6，不被选。k=6。
- 连 4 和 6，不被选。k=6（此时 6 个点成完全图）。
- 连 6 和 7，被选。k=7。
- 连 1 和 7，不被选。k=7。
-
\dots
假设边足够时，被选的边固定在数列 a：1,2,4,7,11,16,22\dots 不难发现是二阶等差数列，通项公式次数为 2。可以用解三元一次方程组等方式发现：
a_i=\frac{1}{2}i^2-\frac{1}{2}i+1
$$
\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 版：
```cpp
#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）：
```cpp
#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);}}
```
[提交记录](https://www.luogu.com.cn/record/215414723)
另一 long long 实现（其实有很多可以省略的代码）：
```cpp
#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;
}
```