题解：AT_abc386_g [ABC386G] Many MST
emmoy
·
·
题解
公式恐惧症慎入。
题目要求边权在 1\sim M 之间，我们转化一下，变成 0\sim M-1 之间，最后再将答案加上 (N-1)\times M^{N(N-1)\over2} 就行了。
对于一个图 G，设 $G_k
为什么？
如果一条边权为 $v$ 边在最小生成树内，那么只有枚举的 $k$ 在 $v+1\sim M$ 的时候才会有这条边，换句话说，也就是才会让联通块数减一。
那么，在这之前，$k$ 从 $1\sim v$ 共 $v$ 次枚举时联通块数会多一，总共就正好加上了 $v$。
减一是因为最小生成树的点数比边数多 $1$。
原式又可化简为 $-M+\sum_{k=1}^{M} c(G_k)$。
设 $S$ 是所有 $M^{N(N+1)\over2}$ 个完全图的集合，$C(G_k)$ 是 $G_k$ 的连通块的集合，那么总答案为：
$$
\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}
$$
到这里应该都挺好理解的。
下面，我们将推导如何为每个 $k$ 求出 $\sum_{G\in S}\sum_{H\in C(G_k)}1$。
对于一个 $H$，我们设它有 $V$ 个点与 $L$ 条边，那么有 $H\in C(G_k)$ 的图 $G\in S$ 的 $H$ 的数量有如下数量个。
$$
(M-k)^{{V(V-1)\over2}-L}\times k^L\times (M-k)^{V(N-V)}\times M^{(N-V)(N-V-1)\over2}
$$
我们考虑 $G$ 中每条边的情况来得出这个式子。
对于两个端点都在 $H$ 中的边，由于只能有 $L$ 条边显示出来，即有 $L$ 条边的权值为 $0\sim k-1$，共 $k$ 种取值，于是一共有 $k^L$ 种情况，剩下共 ${V(V-1)\over2}-L$ 条边由于都没显现出来，于是取值范围从 $k\sim M-1$，共 $M-k$ 种取值，于是有 $(M-k)^{{V(V-1)\over2}-L}$ 种情况。
对于只有一个端点在 $H$ 中的边，由于这种边如果显现，那么 $H$ 就和 $H$ 外的点连接了，与定义不符，于是这种边取值范围从 $k\sim M-1$，共 $M-k$ 种取值，于是有 $(M-k)^{V(N-V)}$ 种情况。
对于两个端点都不在 $H$ 中的边，由于与 $H$ 无关，所以就可以随便选，有 $M^{(N-V)(N-V-1)\over2}$ 种取值。
全部乘起来即可。
---
我们发现后两项只与 $V$ 有关，于是可以设 $f(s)$ 表示有 $s$ 个节点的所有联通块 $H$ 的 $(M-k)^{{s(s-1)\over2}-L}\times k^L$ 的总和。
我们发现我们可以枚举 $s$。
由于我们要在 $N$ 个点中选 $s$ 个点组成联通块，于是要乘上 $\binom{N}{s}$。
根据乘法分配律，原式就可化为：
$$
(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)$。
考虑容斥，于是可以用总方案数减去不构成联通块的方案数。
不构成联通块的方案数就是有小联通块独立出来，这和上面的式子很像。
于是我们直接 copy 过来。
$$
f(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}
$$
于是我们开心的打了代码，发现样例没过。
为什么？
我们发现，由于你连通块外的边乱选，就有可能也组成连通块，于是 $\binom s i$ 的时候会算重。
考虑如何去重。
我们可以钦定一个点一定在所选连通块内，那么无论其他如何组，都因为没有钦定的点而选不到。
于是就相当于 $\binom{s-1}{i-1}$。
原式即为：
$$
f(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}
$$
时间复杂度 $\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;
}
```