Star MST
这个场一大堆 DP，我还都不会做/kk。。。
首先我们需要知道一个性质，对于一张菊花图，要想满足菊花图的最小的生成树，其他不与 1 相连的边 $(u,v)$ 必须满足：
$$\begin{cases}
w(1,u)+w(u,v)\ge w(1,v)+w(1,u)
\\
w(1,v)+w(u,v)\ge w(1,u)+w(1,v)
\end{cases}$$
即满足不管替换哪一条路径 $w(u,v)$ 都不会更优，上面的方程解一下就是 $w(u,v)\ge \max\{w(1,u),w(1,v)\}$。容易明白这个条件是充要的。
那么现在着手 DP。
定义状态 $f(i,j)$，表示已经定好了前 $i$ 个点和它们的连边，其中与 1 相连的边权最大为 $j$，一共有多少种方案。
那么我们考虑转移，我们的一个阶段显然是选择 $p$ 个点与 1 的连边边权是 $j$，不妨直接选择 $p$ 个点与 1 的连边权小于 $j$，并考虑从 $f(p,x)$（$x<j$）转移。
很容易想到我们选择点的方案数是 $\binom{n-p}{i-p}$ 的（从剩下的 $n-p$ 个点选 $i-p$ 个点与 1 相连边权为 $j$）。
很容易想到连边的边数是 $t=(i-p)(p-1)+(i-p)(i-p-1)/2=(i-p)(i+p-3)/2$ 的（即这 $i-p$ 个点与除了 1 的前面的点的连边边权大于 $j$，这 $i-p$ 个点之间相互连边的边权大于 $j$）。
那么我们连边的方案数也就很显然了：$(k-j+1)^t$。
然后我们就有了转移方程：
$$f(i,j)=\sum_{p=1}^{i-1}\left[\left(\sum_{x=0}^{j-1}f(p,x)\right)\binom{n-p}{i-p}(k-j+1)^{(i+p-3)(i-p)/2}\right]$$
这个 $\sum_{x=0}^{j-1}f(p,x)$ 可以预处理，$\binom{n-p}{i-p}$ 可以预处理，$(k-j+1)^{(i+p-3)(i-p)/2}$ 可以快速幂或者光速幂。
初始状态 $f(1,0)=1$。
最后的答案是 $\sum_{i=1}^kf(n,i)$。
时间复杂度 $O(n^2k\log n)$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=3e2,mo=998244353;
ll n,k;
ll comb[N+5][N+5],c[N+5][N+5],f[N+5][N+5];
inline ll Pow(ll b,ll p) {
ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}
inline void Init() {
for(ll i=0;i<=n||i<=k;i++) {
comb[i][0]=1;
for(ll j=1;j<=i;j++) {
comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%mo;
}
}
}
int main() {
n=read();k=read();
Init();
f[1][0]=1;
for(ll i=0;i<=k;i++) c[1][i]=1;
for(ll i=2;i<=n;i++) {
for(ll j=1;j<=k;j++) {
for(ll p=1;p<i;p++) {
ll tmp=c[p][j-1];
tmp=tmp*comb[n-p][i-p]%mo;
ll tmp1=k-j+1,tmp2=(i+p-3)*(i-p)/2;
tmp1=Pow(tmp1,tmp2)%mo;
tmp=tmp*tmp1%mo;
f[i][j]=(f[i][j]+tmp)%mo;
c[i][j]=(c[i][j-1]+f[i][j])%mo;
}
}
}
ll ans=0;
for(ll i=1;i<=k;i++) {ans=(ans+f[n][i])%mo;}
write(ans);
return 0;
}
|