题解：AT_arc165_e [ARC165E] Random Isolation

· · 题解

Sol

不是很简单吧。

考虑可以对一个连通块统计其出现的概率，那么每一个大小超过 k 的连通块，必然会贡献一次，且贡献之后就会变成别的连通块。因此可以把问题转化为各个连通块的出现概率。

一个连通块出现，当且仅当连通块内各点均未被删除，且与连通块相连的非块内点均已被删除。考虑 DP，记 f_{x,i,j} 表示以 x 为根子树中连通块大小为 i 且有 j 个点与这个连通块相连（为了方便转移，不考虑父节点）的概率。转移时对子节点 y 提前使 f_{y,0,1}=1 即可。转移是简单的。

考虑如何计算已知这些限制后这样一个连通块的概率，一个巧妙的转化是，原问题等价于一个 [1,n] 的随机排列 P，顺次遍历这个排列，若当前点所在连通块大小超过 k 就操作，否则跳过，的期望操作次数。这个之所以等价，是因为每次操作后，剩下的有效的点，会等概率出现，因此期望是一样的。

因此相当于一个任意排列上要求 a 个点完全在 b 个点前面的方案数，显然为 \frac{a!b!}{(a+b)!}。

Code

const int N=105;

int n,k;
int sz[N];
mint fc[N],iv[N];
mint f[N][N][N];
mint t[N][N];
vec<int> g[N];
mint ans;

inline void dfs(int x=1,int fa=0){
    f[x][1][0]=1;sz[x]=1;
    for(auto y:g[x])if(y!=fa){
        dfs(y,x);
        f[y][0][1]=1;
        memset(t,0,sizeof t);
        rep(i,0,sz[x])rep(j,0,sz[x])rep(k,0,sz[y])rep(l,0,sz[y])t[i+k][j+l]+=f[x][i][j]*f[y][k][l];
        sz[x]+=sz[y];
        rep(i,0,sz[x])rep(j,0,sz[x])f[x][i][j]=t[i][j];
    }
    auto getans=[&](int a,int b){return fc[a]*fc[b]*iv[a+b];};
    rep(i,k+1,sz[x])rep(j,0,sz[x])ans+=getans(i,j+!!fa)*f[x][i][j];
}

inline void Main(){
    cin>>n>>k;
    fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
    iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;
    repl(i,1,n){
        int a,b;cin>>a>>b;
        g[a].pub(b),g[b].pub(a);
    }
    dfs();
    put(ans);
}