题解：CF1657E Star MST
xiezheyuan
·
·
题解
简要题意
求有多少个有标号 n 个点的无向连通图（每条边的边权位于区间 [1,m]，注意原题面中 m 为 k），使得以 1 为花心的菊花图是这个无向图的一个最小生成树。
答案对 998,244,353 取模。
## 思路
提供一个无需组合数和题意转换的做法。
首先我们需要考虑怎样的树是一个图的最小生成树。假如对于树上每一对不相邻的点 $(x,y)$，原图上的边 $(x,y)$ 的边权比树上路径 $(x,y)$ 的每一条边的边权都要大，那么这就是一个最小生成树。考虑根据这个性质设计 dp 状态。
不妨考虑将原图除了 $1$ 的点重新标号，使得对于 $x<y$，有 $w(1,x)\leq w(1,y)$，其中 $w(a,b)$ 表示完全图上 $(a,b)$ 的权。这样我们就为 dp 钦定了一个合理的顺序。
设 $f(i,j)$ 表示考虑到第 $i$ 个点，$w(1,i)=j$ 的方案数，则不难列出（看起来正确的）转移方程：
$$
f(i,j)=(m-j+1)^{i-1}\cdot \sum_{k=1}^{j-1}f(i-1,k)
$$
其中 $(m-j+1)^{i-1}$ 表示需要满足 $\forall k\lt i, w(k,i)\geq j$。
然后你发现这样是不行的，原因是最后统计答案不方便，最后统计答案的时候，我们要把无标号转换为有标号，这时候直接乘 $(n-1)!$ 是不对的，举个最简单的例子，假如所有 $w(1,i)$ 都相等，这是一种方案，而不是 $(n-1)!$ 种。
你发现罪魁祸首是 $w(1,i)$ 的连续段，考虑将这玩意也设到状态里。
设 $f(i,j,k)$ 表示考虑到第 $i$ 个点，$w(1,i)=j$，之前有 $k-1$ 个 $t$，使得 $w(1,t)=j$ 的方案数。
则先考虑转移 $f(i,j,1)$：
$$
f(i,j,1)=(m-j+1)^{i-1}\cdot \sum_{s=1}^{j-1}\sum_{t=1}^{i-1} \frac{f(i-1,s,t)}{t!}
$$
然后考虑转移 $f(i,j,k)$，其中 $k\geq 2$：
$$
f(i,j,k)=(m-j+1)^{i-1}\cdot f(i-1,j,k-1)
$$
最后答案就是：
$$
(n-1)!\cdot \sum_{s=1}^{m}\sum_{t=1}^{n-1}\frac{f(n-1,s,t)}{t!}
$$
时间复杂度为 $O(n^4\log n)$，无法通过本题，考虑优化。
不妨转换状态，设 $F(i,j,k)=f(i,j,k)\div k!$，你发现转移突然就变得规整了许多：
$$
F(i,j,k)=\begin{cases}
\sum_{s=1}^{j-1}\sum_{t=1}^{i-1}F(s,t)& k=1\\
\frac{1}{k}F(i-1,j,k-1)& \text{otherwise}
\end{cases}
$$
考虑如何优化转移，记：
$$
G(i,j)=\sum_{s=1}^{j}\sum_{t=1}^{i}F(i,s,t)
$$
$G$ 可以在转移的时候计算，那么转移方程就变成了：
$$
F(i,j,k)=\begin{cases}
G(i-1,j-1)& k=1\\
\frac{1}{k}F(i-1,j,k-1)& \text{otherwise}
\end{cases}
$$
答案就是：
$$
(n-1)!\cdot \sum_{s=1}^{m}\sum_{t=1}^{n-1}F(n-1,s,t)
$$
时间复杂度 $O(n^3\log n)$，精细的实现可以做到 $O(n^3)$。
## 代码
```cpp
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 255, mod = 998244353;
int n, m, f[N][N][N], g[N][N], fact[N], inv[N];
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }
int fastpow(int x, int y){
int res = 1;
while(y){
if(y & 1) res = Mul(res, x);
x = Mul(x, x);
y >>= 1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
fact[0] = fact[1] = inv[0] = inv[1] = 1;
for(int i=2;i<=n;i++){
fact[i] = Mul(fact[i - 1], i);
inv[i] = Mul(inv[mod % i], mod - mod / i);
}
for(int i=1;i<=m;i++) f[1][i][1] = 1, g[1][i] = i;
for(int i=2;i<n;i++){
for(int j=1;j<=m;j++){
f[i][j][1] = g[i - 1][j - 1];
f[i][j][1] = Mul(f[i][j][1], fastpow(m - j + 1, i - 1));
g[i][j] = Add(g[i][j - 1], f[i][j][1]);
for(int k=2;k<=i;k++){
f[i][j][k] = Add(f[i][j][k], f[i - 1][j][k - 1]);
f[i][j][k] = Mul(f[i][j][k], Mul(fastpow(m - j + 1, i - 1), inv[k]));
g[i][j] = Add(g[i][j], f[i][j][k]);
}
}
}
int ans = 0;
for(int j=1;j<=m;j++){
for(int k=1;k<=(n - 1);k++) ans = Add(ans, f[n - 1][j][k]);
}
ans = Mul(ans, fact[n - 1]);
cout << ans << '\n';
return 0;
}
// Written by xiezheyuan
```