专栏文章

题解：AT_abc386_g [ABC386G] Many MST

eemmoy
AT_abc386_g题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqlogfh
此快照首次捕获于
2025/12/04 06:50
3 个月前
此快照最后确认于
2025/12/04 06:50
3 个月前
查看原文
公式恐惧症慎入。
题目要求边权在 1∼M1\sim M 之间，我们转化一下，变成 0∼M−10\sim M-1 之间，最后再将答案加上 (N−1)×MN(N−1)2(N-1)\times M^{N(N-1)\over2} 就行了。
对于一个图 GG，设 GkG_k 是由 GG 中边权小于 kk 的边组成的图，而 c(Gk)c(G_k) 是 GkG_k 中连通块的个数，那么其最小生成树的边权和为 ∑k=1M(c(Gk)−1)\sum_{k=1}^{M} (c(G_k)-1)。
为什么？
如果一条边权为 vv 边在最小生成树内，那么只有枚举的 kk 在 v+1∼Mv+1\sim M 的时候才会有这条边，换句话说，也就是才会让联通块数减一。
那么，在这之前，kk 从 1∼v1\sim v 共 vv 次枚举时联通块数会多一，总共就正好加上了 vv。
减一是因为最小生成树的点数比边数多 11。
原式又可化简为 −M+∑k=1Mc(Gk)-M+\sum_{k=1}^{M} c(G_k)。
设 SS 是所有 MN(N+1)2M^{N(N+1)\over2} 个完全图的集合，C(Gk)C(G_k) 是 GkG_k 的连通块的集合，那么总答案为：
(N−1)×MN(N−1)2+∑G∈S(−M+∑k=1Mc(Gk))=(N−1)×MN(N−1)2−M×MN(N−1)2+∑k=1M∑G∈Sc(Gk)=(N−1−M)×MN(N−1)2+∑k=1M∑G∈S∑H∈C(Gk)1\begin{aligned} &(N-1)\times M^{N(N-1)\over2}+\sum_{G\in S}\left(-M+\sum_{k=1}^{M}c(G_k)\right)\\ =&(N-1)\times M^{N(N-1)\over2}-M\times M^{N(N-1)\over2}+\sum_{k=1}^{M}\sum_{G\in S}c(G_k)\\ =&(N-1-M)\times M^{N(N-1)\over2}+\sum_{k=1}^{M}\sum_{G\in S}\sum_{H\in C(G_k)}1 \end{aligned}
到这里应该都挺好理解的。
下面，我们将推导如何为每个 kk 求出 ∑G∈S∑H∈C(Gk)1\sum_{G\in S}\sum_{H\in C(G_k)}1。
对于一个 HH，我们设它有 VV 个点与 LL 条边，那么有 H∈C(Gk)H\in C(G_k) 的图 G∈SG\in S 的 HH 的数量有如下数量个。
(M−k)V(V−1)2−L×kL×(M−k)V(N−V)×M(N−V)(N−V−1)2(M-k)^{{V(V-1)\over2}-L}\times k^L\times (M-k)^{V(N-V)}\times M^{(N-V)(N-V-1)\over2}
我们考虑 GG 中每条边的情况来得出这个式子。
对于两个端点都在 HH 中的边，由于只能有 LL 条边显示出来，即有 LL 条边的权值为 0∼k−10\sim k-1，共 kk 种取值，于是一共有 kLk^L 种情况，剩下共 V(V−1)2−L{V(V-1)\over2}-L 条边由于都没显现出来，于是取值范围从 k∼M−1k\sim M-1，共 M−kM-k 种取值，于是有 (M−k)V(V−1)2−L(M-k)^{{V(V-1)\over2}-L} 种情况。
对于只有一个端点在 HH 中的边，由于这种边如果显现，那么 HH 就和 HH 外的点连接了，与定义不符，于是这种边取值范围从 k∼M−1k\sim M-1，共 M−kM-k 种取值，于是有 (M−k)V(N−V)(M-k)^{V(N-V)} 种情况。
对于两个端点都不在 HH 中的边，由于与 HH 无关，所以就可以随便选，有 M(N−V)(N−V−1)2M^{(N-V)(N-V-1)\over2} 种取值。
全部乘起来即可。
我们发现后两项只与 VV 有关，于是可以设 f(s)f(s) 表示有 ss 个节点的所有联通块 HH 的 (M−k)s(s−1)2−L×kL(M-k)^{{s(s-1)\over2}-L}\times k^L 的总和。
我们发现我们可以枚举 ss。
由于我们要在 NN 个点中选 ss 个点组成联通块，于是要乘上 (Ns)\binom{N}{s}。
根据乘法分配律，原式就可化为：
(N−1−M)×MN(N−1)2+∑k=1M∑s=1N(Ns)f(s)×(M−k)s(N−s)×M(N−s)(N−s−1)2(N-1-M)\times M^{N(N-1)\over2}+\sum_{k=1}^{M}\sum_{s=1}^N\binom N s f(s)\times (M-k)^{s(N-s)}\times M^{(N-s)(N-s-1)\over2}
现在我们的问题是如何快速求出 f(s)f(s)。
考虑容斥，于是可以用总方案数减去不构成联通块的方案数。
不构成联通块的方案数就是有小联通块独立出来，这和上面的式子很像。
于是我们直接 copy 过来。
f(s)=Ms(s−1)2−∑i=1s−1(si)f(i)×(M−k)i(s−i)×M(s−i)(s−i−1)2f(s)=M^{s(s-1)\over2}-\sum_{i=1}^{s-1}\binom s i f(i)\times (M-k)^{i(s-i)}\times M^{(s-i)(s-i-1)\over2}
于是我们开心的打了代码，发现样例没过。
为什么？
我们发现，由于你连通块外的边乱选，就有可能也组成连通块，于是 (si)\binom s i 的时候会算重。
考虑如何去重。
我们可以钦定一个点一定在所选连通块内，那么无论其他如何组，都因为没有钦定的点而选不到。
于是就相当于 (s−1i−1)\binom{s-1}{i-1}。
原式即为：
f(s)=Ms(s−1)2−∑i=1s−1(s−1i−1)f(i)×(M−k)i(s−i)×M(s−i)(s−i−1)2f(s)=M^{s(s-1)\over2}-\sum_{i=1}^{s-1}\binom {s-1} {i-1} f(i)\times (M-k)^{i(s-i)}\times M^{(s-i)(s-i-1)\over2}
时间复杂度 O(n2m)\mathcal{O}(n^2m)。

code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
const int mod=998244353;
int n,m,ans;
int f[N];
int c[N][N],pp[N][N*N];
//c是杨辉三角预处理组合数，pp是预处理幂
signed main()
{
	cin>>n>>m;
	for(int i=0;i<=500;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		pp[i][0]=1;
		for(int j=1;j<=500*500;j++) pp[i][j]=pp[i][j-1]*i%mod;
	}
	ans=(n-1-m)*pp[m][n*(n-1)/2]%mod;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			f[j]=pp[m][j*(j-1)/2];
			for(int k=1;k<j;k++) f[j]=(f[j]-f[k]*c[j-1][k-1]%mod*pp[m-i][k*(j-k)]%mod*pp[m][(j-k)*(j-k-1)/2]%mod+mod)%mod;
			ans=(ans+c[n][j]*f[j]%mod*pp[m-i][j*(n-j)]%mod*pp[m][(n-j)*(n-j-1)/2]%mod)%mod;
		}
	}
	cout<<ans;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...