跳至主要內容

[Medium-Hard] AT_abc386_g [ABC386G] Many MST

xiezheyuan2025/3/22做题笔记组合计数容斥生成树dp图论计数约 1292 字大约 6 分钟

简要题意

计算对于所有 nn 个点的无向完全图（边权位于 [1,m]∩Z[1,m]\cap\mathbb{Z}）的最小生成树边权和之和。答案对 998,244,353998,244,353 取模。

1≤m≤500,2≤n≤5001\leq m\leq 500,2\leq n\leq 500。

思路

先将边权从 [1,n][1,n] 改为 [0,n)[0,n)，这样方便后面拆贡献。下面记 h(x)=(x2)h(x)=\binom{x}{2}。

最小生成树这个东西很难和计数揉在一起，尝试从最小生成树的本质思考。

仿照 Kruskal 算法，我们按照边权从小到大排序，然后尝试加入到最小生成树中。这里将排序改为桶排序，也就是枚举边权，我们称枚举到边权为 xx 称为轮次 xx。

在轮次 xx，我们添加了多少条边？应当是这一轮最后的连通块数，减去上一轮最后的连通块数。记 GkG_k 表示轮次 k−1k-1 已经考虑过的所有边构成的图，τ(G)\tau(G) 表示图 GG 的连通块集合。

那么这个图的最小生成树边权和应该是：

∑k=0mk(τ(Gk)−τ(Gk+1))=∑k=0mkτ(Gk)−∑k=0mkτ(Gk+1)=∑k=0mkτ(Gk)−∑k=1m+1(k−1)τ(Gk)=−mτ(Gm+1)+∑k=1mτ(Gk)=−m+∑k=1mτ(Gk)\begin{aligned} &\sum_{k=0}^{m}k(\tau(G_k)-\tau(G_{k+1}))\\ &=\sum_{k=0}^{m}k\tau(G_k)-\sum_{k=0}^{m}k\tau(G_{k+1})\\ &=\sum_{k=0}^{m}k\tau(G_k)-\sum_{k=1}^{m+1} (k-1)\tau(G_k)\\ &=-m\tau(G_{m+1})+\sum_{k=1}^{m} \tau(G_k)\\ &=-m+\sum_{k=1}^{m}\tau(G_k) \end{aligned}

这个形式看起来好处理一些，代入，则我们要求的是：

(n−1)⋅mh(n)+∑G∑k=1m∣τ(Gk)∣−m=(n−1)⋅mh(n)−m⋅mh(n)+∑G∑k=1m∣τ(Gk)∣=(n−1−m)⋅mh(n)+∑G∑k=1m∑H∈τ(Gk)1=(n−m−1)⋅mh(n)+∑k=1m∑H∑G,H∈τ(Gk)1\begin{aligned} &(n-1)\cdot m^{h(n)}+\sum_{G}\sum_{k=1}^{m} |\tau(G_k)|-m\\ &=(n-1)\cdot m^{h(n)}-m\cdot m^{h(n)}+\sum_{G}\sum_{k=1}^{m} |\tau(G_k)|\\ &=(n-1-m)\cdot m^{h(n)}+\sum_G\sum_{k=1}^{m}\sum_{H\in\tau(G_k)} 1\\ &=(n-m-1)\cdot m^{h(n)}+\sum_{k=1}^{m}\sum_{H}\sum_{G,H\in \tau(G_k)} 1 \end{aligned}

现在考虑如何计算 ∑G,H∈τ(Gk)1\sum_{G,H\in \tau(G_k)} 1，假设 HH 中有 NN 个点，MM 条边。

则有四部分的贡献：

  • 对于 HH 中的边，边权需要位于 [0,k)[0,k)，贡献为 kMk^M。
  • 对于 HH 的导出子图中的非 HH 中的边，边权需要位于 [k,m)[k,m)（因为它们不在 GkG_k 中），贡献为 (m−k)h(N)−M(m-k)^{h(N)-M}。
  • 对于 HH 的点集中的点连向其他点的边，边权需要位于 [k,m)[k,m)（因为它们出现在 GkG_k 中，连通块可以更大），贡献为 (m−k)N(n−N)(m-k)^{N(n-N)}。
  • 对于端点不为 HH 的点集的边，边权没有任何限制（因为它们属于其他连通块），贡献为 mh(n−N)m^{h(n-N)}。

于是得到：

∑G,H∈τ(Gk)1=kM⋅(m−k)h(N)−M⋅(m−k)N(n−N)⋅mh(n−N)\sum_{G,H\in \tau(G_k)} 1=k^M\cdot (m-k)^{h(N)-M}\cdot (m-k)^{N(n-N)}\cdot m^{h(n-N)}

于是现在的目标是求：

∑HkM⋅(m−k)h(N)−M⋅(m−k)N(n−N)⋅mh(n−N)=∑N=1n(m−k)N(n−N)⋅mh(n−N)⋅(nN)⋅∑H=(N,M)kM⋅(m−k)h(N)−M\begin{aligned} &\sum_{H}k^M\cdot (m-k)^{h(N)-M}\cdot (m-k)^{N(n-N)}\cdot m^{h(n-N)}\\ &=\sum_{N=1}^{n}(m-k)^{N(n-N)}\cdot m^{h(n-N)}\cdot\binom{n}{N}\cdot\sum_{H=(N,M)}k^M\cdot (m-k)^{h(N)-M} \end{aligned}

其中添加的 (nN)\binom{n}{N} 表示选出 NN 个点当连通块中的点。

枚举 NN 后只需要求出 ∑H=(N,M)kM⋅(m−k)h(N)−M\sum_{H=(N,M)}k^M\cdot (m-k)^{h(N)-M} 即可。

我们考察这个和式的意义，有多少个 NN 点的无向连通简单图，其中有 kk 种方案选择一条边，有 m−km-k 种方案反选一条边。这是一个很经典的问题的变式。

考虑设 f(N)f(N) 表示上述和式的值，根据我们提出的意义，枚举点 11 所在的连通块大小，可以得到：

mh(N)=∑i=1N(N−1i−1)f(i)⋅mh(N−i)(m−k)i(N−i)m^{h(N)}=\sum_{i=1}^{N}\binom{N-1}{i-1}f(i)\cdot m^{h(N-i)}(m-k)^{i(N-i)}

拉出一个 f(N)f(N) 项，得到：

f(N)=mh(N)−∑i=1N−1(N−1i−1)f(i)⋅mh(N−i)(m−k)i(N−i)f(N)=m^{h(N)}-\sum_{i=1}^{N-1}\binom{N-1}{i-1}f(i)\cdot m^{h(N-i)}(m-k)^{i(N-i)}

直接 dp 可以做到 O(n2)O(n^2)。

故我们可以以 O(n2mlog⁡n)O(n^2m\log n) 的时间复杂度完成本题。可以预处理 mx,(m−k)xm^x,(m-k)^x 做到 O(n2m)O(n^2m)。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

const int N = 505, N_ = N * N;

int h(int x){ return (x * (x - 1)) >> 1; }

int n, m, f[N], pw[N_], pw2[N_], fact[N], inv[N];

int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    fact[0] = inv[0] = 1;
    for(int i=1;i<=n;i++) fact[i] = Mul(fact[i - 1], i), inv[i] = fastpow(fact[i], mod - 2);
    int ans = Mul(Sub(n, Add(m, 1)), fastpow(m, h(n)));
    pw[0] = pw2[0] = 1;
    for(int i=1;i<=n*n;i++) pw[i] = Mul(pw[i - 1], m);
    for(int k=1;k<=m;k++){
        for(int i=1;i<=n*n;i++) pw2[i] = Mul(pw2[i - 1], m - k);
        for(int N=1;N<=n;N++){
            f[N] = pw[h(N)];
            for(int i=1;i<N;i++){
                int tmp = Mul(binom(N - 1, i - 1), f[i]);
                tmp = Mul(tmp, Mul(pw[h(N - i)], pw2[i * (N - i)]));
                f[N] = Sub(f[N], tmp);
            }
            int ret = Mul(pw2[N * (n - N)], pw[h(n - N)]);
            ans = Add(ans, Mul(f[N], Mul(binom(n, N), ret)));
        }
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。