CF1657E

发表于 2022-03-30 分类于 PTS

Star MST

这个场一大堆 DP，我还都不会做/kk。。。

首先我们需要知道一个性质，对于一张菊花图，要想满足菊花图的最小的生成树，其他不与 1 相连的边 $(u, v)$ 必须满足：

${\begin{cases} w (1, u) + w (u, v) \geq w (1, v) + w (1, u) \\ w (1, v) + w (u, v) \geq w (1, u) + w (1, v) \end{cases}$

即满足不管替换哪一条路径 $w (u, v)$ 都不会更优，上面的方程解一下就是 $w (u, v) \geq 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} [(\sum_{x = 0}^{j - 1} f (p, x)) (\binom{n - p}{i - p}) (k - j + 1)^{(i + p - 3) (i - p) / 2}]$

这个 $\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}^{k} f (n, i)$ 。

时间复杂度 $O (n^{2} k \log n)$ 。

代码：

#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;
}